Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParameterized Algorithms for Partial Cover Problems
194
0
0.0
(
0
)
Added by
Saket Saurabh
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$-Edge-Connected and $p$-Vertex-Connected VC problem (where $p geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not admit a polynomial kernel unless $NP subseteq coNP/poly$, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. We obtain an $O(2^{O(pk)}n^{O(1)})$-time algorithm for the $p$-Edge-Connected VC and an $O(2^{O(k^2)}n^{O(1)})$-time algorithm for the $p$-Vertex-Connected VC. Finally, we describe a $2(p+1)$-approximation algorithm for the $p$-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning $p$-vertex/edge-connected subgraph of a $p$-vertex/edge-connected graph obtained independently by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).
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.
We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {sc Test Cover} problem we are given a set $[n]={1,...,n}$ of items together with a collection, $cal T$, of distinct subsets of these items called tests. We assume that $cal T$ is a test cover, i.e., for each pair of items there is a test in $cal T$ containing exactly one of these items. The objective is to find a minimum size subcollection of $cal T$, which is still a test cover. The generic parameterized version of {sc Test Cover} is denoted by $p(k,n,|{cal T}|)$-{sc Test Cover}. Here, we are given $([n],cal{T})$ and a positive integer parameter $k$ as input and the objective is to decide whether there is a test cover of size at most $p(k,n,|{cal T}|)$. We study four parameterizations for {sc Test Cover} and obtain the following: (a) $k$-{sc Test Cover}, and $(n-k)$-{sc Test Cover} are fixed-parameter tractable (FPT). (b) $(|{cal T}|-k)$-{sc Test Cover} and $(log n+k)$-{sc Test Cover} are W[1]-hard. Thus, it is unlikely that these problems are FPT.
After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3^k) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
