Question

The PARTITION INTO PATHS OF
LENGTH 2 problem is as follows:
INSTANCE: A graph, G = (V, E) with IV| = 3q for a positive integer q.
QUESTION: Is there a partition of V into q disjoint subsets VI, V2, ...,
Vq of 3 vertices such that, for each V1 = {Vi[1], Vi[2], Vi[3), at least two of the
three edges {Vi[1], Vi[2], {Vi[1], Vi[3], and {Vi[2], Vi[3]} belong to E?
Prove the PARTITION INTO PATHS OF LENGTH 2 problem is NP-
complete.

Answer 1

Solution

Clearly PARTITION INTO TRIANGLES is in NP because we an first non-deterministically guess a disjoint partition of V and then check (in deterministic polynomial time) that ea h Vi fulfills the triangle condition

We show the NP-hardness by reducing from the NP- complete problem EXACT COVER BY 3-SETS. Assume that we are given a set U such that |U| = 3m for some integer m and a family

F {S1,…..,Sn} of subsets of U such that |Si| = 3 for all i.

We now construct a graph G = V , E with |V} = 3q’ such that G an be partitioned into q’ triangles iff F contains an exact cover for U. We substitute for each set Si = {u, v, w} appearing in F the collection Ei of 18 edges shown below.

The graph G = <V , E> is therefore defined by

Now |V| = |U|+ 9n = 3m + 9n and thus q’ = m + 3n. Note that only the U-vertices may be shared by different E_is.

---

i typed the solution in word when i pasted here, some symbols not working

so i taken screenshot and posted here

if u need original text, let me know

all the best