Nonstandard dual parametrization of graph problems

Question

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).

Answer 1

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

Answer 2

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.