4
$\begingroup$

Suppose we are given a general (connected) undirected graph $G = (V, E)$. An EDGE COVER asks a set $S\subseteq E$ of the minimum number of edges, such that each vertex $v\in V$ is incident to at least one edge $s\in S$. Note that this is solvable in polynomial time.

Now I'd like to generalize this problem to find a set $S$ of vertex-induced connected subgraphs that covers each vertex $v\in V$, but each subgraph $s\in S$ consists of at most (or exactly) 3 vertices (The goal is still to minimize $|S|$). Of course, the topology of a connected subgraph with 3 vertices is fixed (the only way is to form a line with 2 edges connecting them). In other words, we need to find a minimum path cover but the length of each path is at most (or exactly) 3.

Is this problem still poly-time solvable or it's NP-hard? Is it related with 3d matching or steiner tree?

$\endgroup$
2
$\begingroup$

This problem is known to be NP-complete (since the 1970s). Dyer and Frieze established its NP-hardness even for the highly restricted special case where the graph $G$ is planar and bipartite:

Martin E. Dyer, Alan M. Frieze:
On the complexity of partitioning graphs into connected subgraphs.
Discrete Applied Mathematics 10(2): 139-153 (1985)

$\endgroup$
  • $\begingroup$ Are you sure these two are exactly the same problem? I think in your mentioned paper every subgraph should have exactly 3 vertices, which is not the case of this question (which you can have subgraphs of size two or maybe 1). $\endgroup$ – Saeed Mar 27 '17 at 12:18
  • $\begingroup$ @Saeed. Think about it yourself: As the goal is to minimize $|S|$, ... $\endgroup$ – Gamow Mar 27 '17 at 12:29
  • $\begingroup$ @Gamow Thanks for providing the literature. $\endgroup$ – defg Mar 27 '17 at 16:06
  • $\begingroup$ @Gamow, I already thought about it, a simple scenario is that in some circumstances it is not possible to split the graph into even sized components, there are more strange situations: e.g. Consider a star on 9 vertices, there is a minimum size S but there isn't an S which every component has 3 nodes. It is not just simply maximizing one component to fill it with 3 elements. Maybe above paper needs some work to make it a valid solution, if you know that the proof works here as well you can explain it in your answer. $\endgroup$ – Saeed Mar 27 '17 at 17:57
  • $\begingroup$ @Saeed I guess this already shows the NP-completeness of the following decision problem: given a graph with 3n vertices, does there exist a solution of size n? $\endgroup$ – defg Mar 27 '17 at 20:03
0
$\begingroup$

This problem is NP-hard by reduction from 3d matching (3DM). I will refer to your problem as vertex cover with 2-paths.

A 3DM instance consists of element sets $A$, $B$, and $C$ (with $|A| = |B| = |C| = n$) and matching set $S \subseteq A \times B \times C$ (with $|S| = m$). Then the output is "yes" if and only if there exists a subset $S' \subseteq S$ such that each element of $A$, $B$, and $C$ is present in exactly one tuple $(a,b,c)$ from $S'$.

For the reduction, we build a graph $G$ as follows:

The set of vertices of $G$ is $(A \cup B \cup C) \times \{0,1\} \cup S \times \{\alpha, \beta, \gamma\}$. If $x \in A \cup B \cup C$ then there is an edge in $G$ between $(x, 0)$ and $(x, 1)$. If $s = (a,b,c) \in S$ then the following edges are all present in $G$:

  • An edge from $(s, \alpha)$ to $(s, \beta)$
  • An edge from $(s, \beta)$ to $(s, \gamma)$
  • An edge from $(s, \alpha)$ to $(a, 1)$
  • An edge from $(s, \beta)$ to $(b, 1)$
  • An edge from $(s, \gamma)$ to $(c, 1)$

This graph has $6n + 3m$ vertices, so to solve the vertex cover with 2-paths problem on this graph, we would need to use at least $2n+m$ 2-paths (paths of length 2). I will prove below that it is possible to solve the problem with exactly that many 2-paths iff the original 3DM instance was solvable.

First lets do the 3DM solution $\to$ vertex cover with 2-paths solution direction of the proof.

Suppose $S' \subseteq S$ solves the 3DM instance. Then consider the following set of 2-paths:

  • If $s \in S \setminus S'$ then include the 2-path through vertices $(s, \alpha)$, $(s, \beta)$, and $(s, \gamma)$
  • If $s = (a,b,c) \in S'$ then include the 2-path through vertices $(s, \alpha)$, $(a, 1)$, and $(a, 0)$
  • If $s = (a,b,c) \in S'$ then include the 2-path through vertices $(s, \beta)$, $(b, 1)$, and $(b, 0)$
  • If $s = (a,b,c) \in S'$ then include the 2-path through vertices $(s, \alpha)$, $(c, 1)$, and $(c, 0)$

The four bullet points above describe $m-n$, $n$, $n$, and $n$ 2-paths respectively. This is a total of $2n+m$ 2-paths. Provided these 2-paths touch every vertex in $G$, they form a solution to the vertex cover with 2-paths problem.

Clearly, every vertex in $S \times \{\alpha, \beta, \gamma\}$ is on some 2-path from the above list.

Next consider any vertex $(a, i) \in A \times \{0,1\}$. Since $S'$ is a solution to the 3DM instance, some $s \in S'$ has $a$ as the first coordinate. The 2-path from $(s, \alpha)$ to $(a, 1)$ to $(a, 0)$ includes the vertex in question.

Similarly, if $(b, i) \in B \times \{0,1\}$ then some $s \in S'$ has $b$ as the second coordinate and the 2-path from $(s, \beta)$ to $(b, 1)$ to $(b, 0)$ includes the vertex in question. Similarly, if $(c, i) \in C \times \{0,1\}$ then some $s \in S'$ has $c$ as the third coordinate and the 2-path from $(s, \gamma)$ to $(c, 1)$ to $(c, 0)$ includes the vertex in question.

We see that in this case there exists a choice of $m+2n$ 2-paths that cover every vertex.

Next lets do the vertex cover with 2-paths solution $\to$ 3DM solution direction of the proof.

Suppose we have exactly $m+2n$ 2-paths in $G$ covering every vertex.

Consider any $a \in A$. Since $(a,1)$ is the only neighbor of $(a,0)$ in $G$ and since all other neighbors of $(a,1)$ are of the form $((a,b,c), \alpha)$, it must be the case that one of the 2-paths used is of the form $(a, 0)$, $(a, 1)$, $((a,b,c), \alpha)$.

We can do the same thing with any $b \in B$ or $c \in C$ (i.e. if $b \in B$ then there must be a 2-path in the solution of the form $(b,0)$, $(b,1)$, $((a,b,c), \beta)$). In general, for every $x \in A \cup B \cup C$, there will be a 2-path in the solution of the form $(x, 0)$, $(x, 1)$, $(s, i)$ (where $i \in \{\alpha, \beta, \gamma\}$). Call these the type-1 2-paths.

Consider the remaining 2-paths in the solution. Call these the type-2 2-paths. The type-2 2-paths must use exactly the vertices not used by the type-1 2-paths. Then since every vertex in $(A \cup B \cup C) \times \{0,1\}$ is in a type-1 2-path, every type-2 2-path will consist of three vertices from $S \times \{\alpha, \beta, \gamma\}$. The only 2-paths in $G$ of this form are the 2-paths over vertices $(s, \alpha)$, $(s, \beta)$, $(s, \gamma)$ for some $s \in S$. Therefore, for every $s \in S$, either the three vertices $(s, \alpha)$, $(s, \beta)$, and $(s, \gamma)$ are used together in a type-2 2-path or they are each used in a type-1 2-path.

Let $S'$ be the set of $s \in S$ such that vertices $(s, \alpha)$, $(s, \beta)$, and $(s, \gamma)$ are each used in a type-1 2-path. Notice that $|S'| = n$. Notice also that each $a \in A$ is the first coordinate of exactly one $s \in S'$ in particular, $a$ is the first coordinate of the $s$ for which $(a,0)$, $(a,1)$, $(s, \alpha)$ is a type-1 2-path. Similarly, every $b \in B$ (or $c \in C$) is the second (or third) coordinate of exactly one $s\in S'$. In other words, $S'$ solves the 3DM instance.

$\endgroup$
  • $\begingroup$ I just read the first two paragraphs of your proof, deciding whether the set S' exists or not is trivial: either S satisfies the condition or not, that's all. You forgot the restriction that size of S' should be smaller than some given number k. Maybe your proof is correct (I didn't read it), but your definition of 3DM is not correct. $\endgroup$ – Saeed Mar 27 '17 at 12:14
  • $\begingroup$ @Saeed Thanks for the comment. I realize now that my statement of 3DM is ambiguous. The condition on $S'$ that I wrote was "each element of $A$, $B$, and $C$ is present in some tuple $(a,b,c)$ from $S'$ exactly once", but what I was trying to say was "each element of $A$, $B$, and $C$ is present in exactly one tuple $(a,b,c)$ from $S'$." Do you agree that this matches the actual definition of 3DM (or maybe this is called 3d perfect matching, I don't know)? Do you think I should edit the post with that change? Note that the rest of the proof uses the definition I meant to write. $\endgroup$ – Mikhail Rudoy Mar 27 '17 at 18:05
  • $\begingroup$ @Saeed 3DM asks an S' with size n. $\endgroup$ – defg Mar 27 '17 at 19:50
  • $\begingroup$ @MikhailRudoy, That was a good point, but I didn't point out to that problem, I said you didn't define the size of S' in the definition. $\endgroup$ – Saeed Mar 28 '17 at 10:42
  • $\begingroup$ @defg, I did not ask what is 3dm, I said the problem definition is not complete, it is better to either write the problem definition completely or do not write it at all. $\endgroup$ – Saeed Mar 28 '17 at 10:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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