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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Do you mind if the problem introduces weights? $\endgroup$– SaeedFeb 3, 2017 at 20:06
-
2$\begingroup$ 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... $\endgroup$– danielloFeb 3, 2017 at 20:30
-
$\begingroup$ 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. $\endgroup$– JuhoFeb 3, 2017 at 20:32
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
$(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 - 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.
-
$\begingroup$ 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. $\endgroup$– danielloJul 6, 2017 at 9:44
$\begingroup$
$\endgroup$
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, 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 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$.
$\begingroup$
$\endgroup$
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:
- A graph $G=(V,E)$, with a capacity function on vertices $c:V\rightarrow N$.
- $k$ source and terminal pairs $(s_1,t_1),\ldots,(s_k,t_k)\subseteq V\times V$.
- $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.
