3
$\begingroup$

We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges.

The problem is similar to the partition into triangles problem (which is NP-complete) but not the same because each subgraphs may contain 2 or 3 edges (unlike the triangles problem, which requires 3 edges in each subgraph).

Is there a polynomial-time algorithm for this problem?

$\endgroup$

1 Answer 1

1
$\begingroup$

The problem can be equivalently stated as follows:

Can a graph be partitioned into vertex disjoint paths of lengths $3$?

The problem is shown to be $\mathsf{NP}$-hard (see Theorem 1 here).

Note that the proof is given for $k$-partition problem. However, it holds for your problem as well. In the proof, the partitions must contain $3$ vertices; note the following statement written in the proof: "We claim that $S'$ can be partitioned into members of $C$ if and only if $G$ can be partitioned into $p = p' + 3q'$ paths of length at most $3$. Since $|V| = 3p$, if $G$ can be partitioned into $p$ paths of length at most $3$, then each of these paths must have exactly $3$ vertices on it."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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