A generalization of edge cover

Question

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?

Answer 1

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)

Answer 2

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.