<p>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. </p>

<p>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), <a href="http://dx.doi.org/10.1007/s00224-012-9393-4" rel="nofollow noreferrer">http://dx.doi.org/10.1007/s00224-012-9393-4</a>).</p>

<p>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$.</p>

<p>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:</p>

<p>Johannes Uhlmann, Mathias Weller:
Two-Layer Planarization parameterized by feedback edge set. Theor. Comput. Sci. 494: 99-111 (2013), <a href="http://dx.doi.org/10.1016/j.tcs.2013.01.029" rel="nofollow noreferrer">http://dx.doi.org/10.1016/j.tcs.2013.01.029</a></p>

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

<p>Sepp Hartung, Christian Komusiewicz, André Nichterlein:
Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs. J. Graph Algorithms Appl. 19(1): 155-190 (2015), <a href="http://dx.doi.org/10.7155/jgaa.00352" rel="nofollow noreferrer">http://dx.doi.org/10.7155/jgaa.00352</a></p>

CC BY-SA 3.0
2016-12-03T07:52:16.020Z
Yes, thanks for pointing this out. I changed this part to a kernelization for the feedback edge number which is smaller.
Christian Komusiewicz
CC BY-SA 3.0
2016-12-05T10:53:58.763Z
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?
Florent Foucaud
CC BY-SA 3.0
2016-12-02T22:51:23.077Z
2016-12-03T07:51:29.483Z
2016-12-03T07:51:29.483Z
Christian Komusiewicz
<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2016-12-02T12:14:36.393Z
Thanks, neat! If you know a reference where such parameter is studied (for other graph problems), please let me know.
Florent Foucaud
CC BY-SA 3.0
2016-12-01T14:18:03.797Z
2016-12-01T14:18:03.797Z
Michael Lampis
<p>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.</p>

<p>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?</p>

<p><i><b>Note:</b> 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 <b>hypergraph</b> problem TEST COVER in the 2012 paper "<a href="http://link.springer.com/chapter/10.1007/978-3-642-32589-2_27" rel="nofollow noreferrer">Parameterized Study of the Test Cover Problem</a>" by Crowston, Gutin, Jones, Saurabh and Yeo. (also <a href="https://arxiv.org/abs/1212.0117" rel="nofollow noreferrer">on arXiv</a>)</p>

<p><b>Edit (04/12/2016):</b> This parameterization is also studied for the other hypergraph problem HITTING SET in the 2011 paper <a href="http://www.sciencedirect.com/science/article/pii/S0304397511005378" rel="nofollow noreferrer">Kernels for below-upper-bound parameterizations of the hitting set and
directed dominating set problems</a> by Gutin, Mones and Yeo (<a href="https://arxiv.org/abs/1010.5881" rel="nofollow noreferrer">arXiv link</a>).</i></p>

<reference-request><graph-algorithms><fixed-parameter-tractable>
Nonstandard dual parametrization of graph problems
Florent Foucaud
# Nonstandard dual parametrization of graph problems

(Asked by: username_0 on 2016-12-01)

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](http://link.springer.com/chapter/10.1007/978-3-642-32589-2_27)" by Crowston, Gutin, Jones, Saurabh and Yeo. (also [on arXiv](https://arxiv.org/abs/1212.0117))*

**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](http://www.sciencedirect.com/science/article/pii/S0304397511005378) by Gutin, Mones and Yeo ([arXiv link](https://arxiv.org/abs/1010.5881)).

**Tags:** reference-request, graph-algorithms, fixed-parameter-tractable


---

## 2 answers

### Answer by username_1 on 2016-12-02. Score: 5 | Accepted answer

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, username_1, 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>

> **Comments:**
> **username_1**: Yes, thanks for pointing this out. I changed this part to a kernelization for the feedback edge number which is smaller.  
> **username_0**: 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?  

---

### Answer by username_2 on 2016-12-01. Score: 9

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.

> **Comments:**
> **username_0**: Thanks, neat! If you know a reference where such parameter is studied (for other graph problems), please let me know.  

---

