8
$\begingroup$

One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when parameterized by the "dual parameter" $|V(G)|-k$, it becomes equivalent to INDEPENDENT SET parameterized by solution size (because any vertex cover is the complement of an independent set), and thus it is W[1]-hard.

Although this seems less natural, I am interested in the parameterized complexity of VERTEX COVER for the parameter $|E(G)|-k$. This is a larger parameter than $|V(G)|-k$. Is VERTEX COVER FPT for this parameter?

Note: I am also interested in similar parameterizations for other graph problems (e.g. DOMINATING SET). The only place where I have seen both kinds of dual parameters studied is for the hypergraph problem TEST COVER in the 2012 paper "Parameterized Study of the Test Cover Problem" by Crowston, Gutin, Jones, Saurabh and Yeo. (also on arXiv)

Edit (04/12/2016): This parameterization is also studied for the other hypergraph problem HITTING SET in the 2011 paper Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems by Gutin, Mones and Yeo (arXiv link).

$\endgroup$
5
$\begingroup$

Let $n:=|V(G)|$ and $m:= |E(G)|$. The dual parameter $m-k$ is always at least as large as $m-n$ which in turn is at least as large as the size of a feedback edge set, a set of edges whose removal makes $G$ acyclic.

The size of a smallest feedback edge set, let's call it feedback edge number $\phi$, is also at least as large as the feedback vertex number and the treewidth of the graph. This directly implies that Vertex Cover is fixed-parameter tractable for $m-k$. Moreover, it has a polynomial kernel since Vertex Cover parameterized by feedback vertex number has one (this was shown by Jansen and Bodlaender in Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter. Theory Comput. Syst. 53(2): 263-299 (2013), http://dx.doi.org/10.1007/s00224-012-9393-4).

A simple direct linear kernel for Vertex Cover parameterized by feedback edge number $\phi$ should be obtainable as follows: Remove all degree-0 vertices, add the neighbor of any degree-1 vertex to the vertex cover, and reduce paths of degree-2 vertices that contain at least 2 vertices (decreasing the bound on $k$ accordingly). After exhaustive application of these reduction rules, in the resulting graph $n=O(\phi)$. This directly implies a kernel for the larger parameter $m-k$.

To answer your question for references: I would look for feedback edge number which is smaller than the dual parameter $m-k$, has been considered in the literature, and often gives fixed-parameter tractability results also for Dominating Set (as the parameter is quite large). Here are three further examples:

Johannes Uhlmann, Mathias Weller: Two-Layer Planarization parameterized by feedback edge set. Theor. Comput. Sci. 494: 99-111 (2013), http://dx.doi.org/10.1016/j.tcs.2013.01.029

André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller: On tractable cases of Target Set Selection. Social Netw. Analys. Mining 3(2): 233-256 (2013), http://dx.doi.org/10.1007/s13278-012-0067-7

Sepp Hartung, Christian Komusiewicz, André Nichterlein: Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs. J. Graph Algorithms Appl. 19(1): 155-190 (2015), http://dx.doi.org/10.7155/jgaa.00352

$\endgroup$
  • $\begingroup$ If there are any, then "Remove all degree-0 vertices" decreases n without changing m, so increases m-n. ​ Accordingly, the resulting graph's size being linear in the resulting graph's parameter does not mean the resulting graph's size has any bound in terms of the input graph's parameter. ​ ​ ​ ​ $\endgroup$ – user6973 Dec 3 '16 at 0:28
  • $\begingroup$ Yes, thanks for pointing this out. I changed this part to a kernelization for the feedback edge number which is smaller. $\endgroup$ – C Komus Dec 3 '16 at 7:52
  • 2
    $\begingroup$ Subsidiary question: the 2 papers I pointed to were for hypergraph problems, but there $m-k$ is not necessary larger than $n-k$ since there can less hyperedges than vertices. Is there soem generic trick that works there? $\endgroup$ – Florent Foucaud Dec 5 '16 at 10:53
9
$\begingroup$

I think this problem is FPT. Suppose that the graph contains a path on $2k+1$ vertices. Then, I claim the answer is YES: we select the second, fourth, sixth, etc. vertices of this path in a solution and remove them from the graph. We now have a graph $G'$ with $|E(G')|\le |E(G)|-2k$. It is easy to find a vertex cover of $G'$ with size at most $|E(G')|$. Together with the removed vertices this gives a vertex cover of size at most $|E(G)|-k$ for $G$.

If the graph does not contain a path on $2k+1$ vertices, then a DFS tree of the graph has height at most $2k+1$, and hence can be used to construct a tree decomposition of width at most $2k$. We can then solve Vertex Cover optimally with the standard algorithm for treewidth.

$\endgroup$
  • $\begingroup$ Thanks, neat! If you know a reference where such parameter is studied (for other graph problems), please let me know. $\endgroup$ – Florent Foucaud Dec 2 '16 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.