Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Linear Time Parameterized Algorithm for Node Unique Label Cover
124
0
0.0
(
0
)
Added by
Ramanujan M. S.
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The optimization version of the Unique Label Cover problem is at the heart of the Unique Games Conjecture which has played an important role in the proof of several tight inapproximability results. In recent years, this problem has been also studied extensively from the point of view of parameterized complexity. Cygan et al. [FOCS 2012] proved that this problem is fixed-parameter tractable (FPT) and Wahlstrom [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlstrom and Yoshida [2014] proved that the edge version of Unique Label Cover can be solved in linear FPT-time. That is, there is an FPT algorithm whose dependence on the input-size is linear. However, such an algorithm for the node version of the problem was left as an open problem. In this paper, we resolve this question by presenting the first linear-time FPT algorithm for Node Unique Label Cover.
rate research
Read More
In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph $D$ on $n$ vertices and $m$ edges, and an integer $k$. The objective is to determine whether there exists a set of at most $k$ vertices intersecting every directed cycle of $D$. Whether or not DFVS admits a fixed parameter tractable (FPT) algorithm was considered the most important open problem in parameterized complexity until Chen, Liu, Lu, OSullivan and Razgon [JACM 2008] answered the question in the affirmative. They gave an algorithm for the problem with running time $O(k!4^kk^4nm)$. Since then, no faster algorithm for the problem has been found. In this paper, we give an algorithm for DFVS with running time $O(k!4^kk^5(n+m))$. Our algorithm is the first algorithm for DFVS with linear dependence on input size. Furthermore, the asymptotic dependence of the running time of our algorithm on the parameter $k$ matches up to a factor $k$ the algorithm of Chen, Liu, Lu, OSullivan and Razgon. On the way to designing our algorithm for DFVS, we give a general methodology to shave off a factor of $n$ from iterative-compression based algorithms for a few other well-studied covering problems in parameterized complexity. We demonstrate the applicability of this technique by speeding up by a factor of $n$, the current best FPT algorithms for Multicut [STOC 2011, SICOMP 2014] and Directed Subset Feedback Vertex Set [ICALP 2012, TALG 2014].
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems have been intensively studied in planar graphs and in graphs excluding a fixed graph $H$ as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.
We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of $m$ sets over $n$ elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight query complexities. On one hand, first we show an adaptation of the streaming algorithm presented in Har-Peled et al. [2016] to the sub-linear query model, that returns an $alpha$-approximate cover using $tilde{O}(m(n/k)^{1/(alpha-1)} + nk)$ queries to the input, where $k$ denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of $k$, the required number of queries is $tilde{Omega}(m(n/k)^{1/(2alpha)})$, even for estimating the optimal cover size. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require $Omega(nk)$ queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter $k$. On the other hand, we show that this bound is not optimal for larger values of the parameter $k$, as there exists a $(1+varepsilon)$-approximation algorithm with $tilde{O}(mn/kvarepsilon^2)$ queries. We show that this bound is essentially tight for sufficiently small constant $varepsilon$, by establishing a lower bound of $tilde{Omega}(mn/k)$ query complexity.
In the Disjoint Paths problem, the input is an undirected graph $G$ on $n$ vertices and a set of $k$ vertex pairs, ${s_i,t_i}_{i=1}^k$, and the task is to find $k$ pairwise vertex-disjoint paths connecting $s_i$ to $t_i$. The problem was shown to have an $f(k)n^3$ algorithm by Robertson and Seymour. In modern terminology, this means that Disjoint Paths is fixed parameter tractable (FPT), parameterized by the number of vertex pairs. This algorithm is the cornerstone of the entire graph minor theory, and a vital ingredient in the $g(k)n^3$ algorithm for Minor Testing (given two undirected graphs, $G$ and $H$ on $n$ and $k$ vertices, respectively, the objective is to check whether $G$ contains $H$ as a minor). All we know about $f$ and $g$ is that these are computable functions. Thus, a challenging open problem in graph algorithms is to devise an algorithm for Disjoint Paths where $f$ is single exponential. That is, $f$ is of the form $2^{{sf poly}(k)}$. The algorithm of Robertson and Seymour relies on topology and essentially reduces the problem to surface-embedded graphs. Thus, the first major obstacle that has to be overcome in order to get an algorithm with a single exponential running time for Disjoint Paths and {sf Minor Testing} on general graphs is to solve Disjoint Paths in single exponential time on surface-embedded graphs and in particular on planar graphs. Even when the inputs to Disjoint Paths are restricted to planar graphs, a case called the Planar Disjoint Paths problem, the best known algorithm has running time $2^{2^{O(k)}}n^2$. In this paper, we make the first step towards our quest for designing a single exponential time algorithm for Disjoint Paths by giving a $2^{O(k^2)}n^{O(1)}$-time algorithm for Planar Disjoint Paths.
We study the problem of Imbalance parameterized by the twin cover of a graph. We show that Imbalance is XP parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest clique outside the twin cover. In contrast, we introduce a notion of succinct representations of graphs in terms of their twin cover and demonstrate that Imbalance is NP-hard in the setting of succinct representations, even for graphs that have a twin cover of size one.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
