<p>Here is a problem (with lists!) which is known to be W[1]-hard parameterized by Vertex Cover (indeed, even by the number of vertices in the input graph). The problem is known as the "<strong>Arc Supply</strong>" problem, and it was proved W[1]-hard (parameterized by the number of vertices) by <a href="http://dl.acm.org/citation.cfm?id=1696675" rel="nofollow noreferrer">Bodlaender, myself and Penninkx</a>, even on planar graphs.</p>

<p>Input is a simple directed (planar) graph $G$ with $k$ vertices. Furthermore, every vertex $v$ has a positive integer <em>demand</em>. Every edge $e$ has a list $L_e$ of <em>supply pairs</em>: 
$$L_e = \{(x_1^e, y_1^e), (x_2^e, y_2^e), \ldots, (x_\ell^e, y_\ell^e)\}.$$ 
Here $x_i^e$ and $y_i^e$ are positive integers. All integers are encoded in unary. Different edges may have different lists. </p>

<p>The task is to select one supply pair from each of the lists of all the edges. If the pair $(x_i^e, y_i^e)$ is selected from the list of the edge $e$ from $u$ to $v$, then the edge <em>supplies</em> $x_i$ towards the demand of $u$ and $y_i$ towards the demand of $v$. A vertex gets <em>satisfied</em> if the total supply it gets from all of its edges is at least its demand. The goal is to satisfy all of the vertices simultaneously. </p>

<p>Note that the problem <em>does</em> have an $n^{O(c)}$ time (dynamic programming) algorithm on graphs with a vertex cover of size $c$, here $n$ is the total input size. </p>

<hr>

<p><strong>Expanded from my comment:</strong> It would be very surprising if some problem where the graph is the only input (i,e no lists / weights, etc) is W[1]-hard when parameterized by Vertex Cover, because instances with a vertex cover of size $k$ can be encoded with $2^k \log n$ bits, so a reduction from $k$-Clique to the problem would have to compress $n^2$ bits to $2^k \log n$ bits in FPT time. </p>

<p>I would speculate that it is possible to use the incompressibility result of <a href="http://dl.acm.org/citation.cfm?doid=2629620" rel="nofollow noreferrer">Dell and van Melkebeek</a> for the Clique problem (in essence that no polynomial time procedure can reduce the input to $n^{2-\epsilon}$ bits) to prove that a <em>polynomial time</em> reduction showing W[1] hardness parameterized by Vertex Cover of <em>any</em> parameterized language where the graph is the only input would imply $coNP \subseteq NP/poly$. </p>

CC BY-SA 3.0
2017-07-05T11:27:19.433Z
2017-07-06T19:05:12.053Z
2017-07-06T19:05:12.053Z
daniello
<p>$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos <a href="https://arxiv.org/abs/1704.08868" rel="noreferrer">here</a> - sorry about the self-promotion!). The problem here is to select $k$ vertices (centers) so that all other vertices are at distance at most $r$ from the closest center. This generalizes $k$-Dominating Set (which corresponds to $r=1$). More strongly, the problem is $W[1]$-hard parameterized by vertex cover and $k$.</p>

<p>The catch with our reduction is that we need to produce an edge-weighted graph, i.e. we need the edges to have different lengths. We can replace weighted edges with paths, but then this only proves W-hardness when the problem is parameterized by feedback vertex set. Indeed, if all edges have uniform weights then the problem is FPT parameterized by vertex cover. </p>

<p>This example reinforces Daniel's point (which I agree with) that it would be surprising to find a problem that is W-hard by vertex cover, without having some additional input given besides the graph.</p>

CC BY-SA 3.0
2017-07-06T09:44:31.660Z
Oh, thats cute! As an example of a hard problem parameterized by Vertex Cover (and not #vertices like my example, or say grid tiling) this is the most natural one I've seen so far, other than List Coloring.
daniello
CC BY-SA 3.0
2017-07-05T23:53:16.143Z
2017-07-05T23:53:16.143Z
Michael Lampis
<p>I don't know if there is any pure graph theoretic problem which is hard in bounded vertex cover, and if there is any it is very interesting for me to see such problem. However, here is a problem of weighted disjoint paths with congestion, a natural practical and theoretical problem. </p>

<p><strong>Input:</strong> </p>

<ol>
<li>A graph $G=(V,E)$, with a capacity function on vertices $c:V\rightarrow N$.</li>
<li>$k$ source and terminal pairs $(s_1,t_1),\ldots,(s_k,t_k)\subseteq V\times V$.</li>
<li>$k$ integers $d_1,\ldots,d_k$ as demands. </li>
</ol>

<p><strong>Output:</strong> Find $k$ edge disjoint paths $P_1,\ldots,P_k$ such that $P_i$ connects $s_i$ to $t_i$ and additionally sum of demands of all paths going through any vertex $v$ is at most $c(v)$.</p>

<p>We can show the problem is NP-hard even if the vertex cover has size 2:</p>

<p>Consider the following instance of a graph and demands.</p>

<p>Vertex Sets: $s_1,\ldots,s_k,t_1,\ldots,t_k,u,v$. 
Edge sets: $(s_i,u),(s_i,v),(v,t_i),(u,t_i)$ for $i\in [k]$.
Demands: arbitrary even integers $d_1,\ldots,d_k$.
Capacity: $c(u)=c(v)=\Sigma {d_i}/2$. All other vertices have infinite capacity.</p>

<p>We want to find paths between sources ($s_i$'s) and terminals ($t_i$'s). </p>

<p>It is clear that $u,v$ cover all edges of the graph, also it is easy to see if there is a polynomial time algorithm for this then $2$-Partition problem is in P.</p>

CC BY-SA 3.0
2017-02-04T21:56:35.697Z
2017-07-10T10:01:56.890Z
2017-07-10T10:01:56.890Z
Saeed
<p>We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?</p>

CC BY-SA 3.0
2017-02-03T20:06:50.370Z
Do you mind if the problem introduces weights?
Saeed
CC BY-SA 3.0
2017-02-03T20:30:01.310Z
It would be very surprising if some problem where the graph is the only input (i,e no lists / weights, etc) is hard when parameterized by Vertex Cover, because instances with a vertex cover of size k can be encoded with $2^k \log n$ bits, so a reduction from $k$-Clique to the problem would have to compress $n^2$ bits to $2^k \log n$ in FPT time. With weights / lists one should be able to cook up some more or less natural problems...
daniello
CC BY-SA 3.0
2017-02-03T20:32:52.777Z
Just a related remark: I think that list L(1,1)-labeling is NPC for constant values of the vertex cover number. But besides list coloring, I don't know of any natural problems that fit what you ask.
Juho
<graph-algorithms><graph-colouring><parameterized-complexity><fixed-parameter-tractable>
Hard problems for bounded vertex cover
Kumar
# Hard problems for bounded vertex cover

(Asked by: username_0 on 2017-02-01)

We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?

**Tags:** graph-algorithms, graph-colouring, parameterized-complexity, fixed-parameter-tractable

> **Comments:**
> **username_1**: Do you mind if the problem introduces weights?  
> **username_2**: It would be very surprising if some problem where the graph is the only input (i,e no lists / weights, etc) is hard when parameterized by Vertex Cover, because instances with a vertex cover of size k can be encoded with $2^k \log n$ bits, so a reduction from $k$-Clique to the problem would have to compress $n^2$ bits to $2^k \log n$ in FPT time. With weights / lists one should be able to cook up some more or less natural problems...  
> **username_3**: Just a related remark: I think that list L(1,1)-labeling is NPC for constant values of the vertex cover number. But besides list coloring, I don't know of any natural problems that fit what you ask.  

---

## 3 answers

### Answer by username_4 on 2017-07-05. Score: 7

$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos [here](https://arxiv.org/abs/1704.08868) - sorry about the self-promotion!). The problem here is to select $k$ vertices (centers) so that all other vertices are at distance at most $r$ from the closest center. This generalizes $k$-Dominating Set (which corresponds to $r=1$). More strongly, the problem is $W[1]$-hard parameterized by vertex cover and $k$.

The catch with our reduction is that we need to produce an edge-weighted graph, i.e. we need the edges to have different lengths. We can replace weighted edges with paths, but then this only proves W-hardness when the problem is parameterized by feedback vertex set. Indeed, if all edges have uniform weights then the problem is FPT parameterized by vertex cover.

This example reinforces Daniel's point (which I agree with) that it would be surprising to find a problem that is W-hard by vertex cover, without having some additional input given besides the graph.

> **Comments:**
> **username_2**: Oh, thats cute! As an example of a hard problem parameterized by Vertex Cover (and not #vertices like my example, or say grid tiling) this is the most natural one I've seen so far, other than List Coloring.  

---

### Answer by username_2 on 2017-07-05. Score: 6

Here is a problem (with lists!) which is known to be W[1]-hard parameterized by Vertex Cover (indeed, even by the number of vertices in the input graph). The problem is known as the "**Arc Supply**" problem, and it was proved W[1]-hard (parameterized by the number of vertices) by [Bodlaender, myself and Penninkx](http://dl.acm.org/citation.cfm?id=1696675), even on planar graphs.

Input is a simple directed (planar) graph $G$ with $k$ vertices. Furthermore, every vertex $v$ has a positive integer *demand*. Every edge $e$ has a list $L\_e$ of *supply pairs*:
$$L\_e = \{(x\_1^e, y\_1^e), (x\_2^e, y\_2^e), \ldots, (x\_\ell^e, y\_\ell^e)\}.$$
Here $x\_i^e$ and $y\_i^e$ are positive integers. All integers are encoded in unary. Different edges may have different lists.

The task is to select one supply pair from each of the lists of all the edges. If the pair $(x\_i^e, y\_i^e)$ is selected from the list of the edge $e$ from $u$ to $v$, then the edge *supplies* $x\_i$ towards the demand of $u$ and $y\_i$ towards the demand of $v$. A vertex gets *satisfied* if the total supply it gets from all of its edges is at least its demand. The goal is to satisfy all of the vertices simultaneously.

Note that the problem *does* have an $n^{O(c)}$ time (dynamic programming) algorithm on graphs with a vertex cover of size $c$, here $n$ is the total input size.

---

**Expanded from my comment:** It would be very surprising if some problem where the graph is the only input (i,e no lists / weights, etc) is W[1]-hard when parameterized by Vertex Cover, because instances with a vertex cover of size $k$ can be encoded with $2^k \log n$ bits, so a reduction from $k$-Clique to the problem would have to compress $n^2$ bits to $2^k \log n$ bits in FPT time.

I would speculate that it is possible to use the incompressibility result of [Dell and van Melkebeek](http://dl.acm.org/citation.cfm?doid=2629620) for the Clique problem (in essence that no polynomial time procedure can reduce the input to $n^{2-\epsilon}$ bits) to prove that a *polynomial time* reduction showing W[1] hardness parameterized by Vertex Cover of *any* parameterized language where the graph is the only input would imply $coNP \subseteq NP/poly$.


---

### Answer by username_1 on 2017-02-04. Score: 4

I don't know if there is any pure graph theoretic problem which is hard in bounded vertex cover, and if there is any it is very interesting for me to see such problem. However, here is a problem of weighted disjoint paths with congestion, a natural practical and theoretical problem.

**Input:**

1. A graph $G=(V,E)$, with a capacity function on vertices $c:V\rightarrow N$.
2. $k$ source and terminal pairs $(s\_1,t\_1),\ldots,(s\_k,t\_k)\subseteq V\times V$.
3. $k$ integers $d\_1,\ldots,d\_k$ as demands.

**Output:** Find $k$ edge disjoint paths $P\_1,\ldots,P\_k$ such that $P\_i$ connects $s\_i$ to $t\_i$ and additionally sum of demands of all paths going through any vertex $v$ is at most $c(v)$.

We can show the problem is NP-hard even if the vertex cover has size 2:

Consider the following instance of a graph and demands.

Vertex Sets: $s\_1,\ldots,s\_k,t\_1,\ldots,t\_k,u,v$.
Edge sets: $(s\_i,u),(s\_i,v),(v,t\_i),(u,t\_i)$ for $i\in [k]$.
Demands: arbitrary even integers $d\_1,\ldots,d\_k$.
Capacity: $c(u)=c(v)=\Sigma {d\_i}/2$. All other vertices have infinite capacity.

We want to find paths between sources ($s\_i$'s) and terminals ($t\_i$'s).

It is clear that $u,v$ cover all edges of the graph, also it is easy to see if there is a polynomial time algorithm for this then $2$-Partition problem is in P.


---

