The Partition into paths of length 2 problem is as follows I

The Partition into paths of length 2 problem is as follows: Instance: A graph, G = (V,E) with |V| = 3q for a positive integer q.

Question: is there a partition of V into q disjoint subsets V1,V2..Vq of 3 vertices such that for each Vi = {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

I am looking for the proof

Solution

Let G = (V, E) be the graph obtained from the union of the gadgets H(xi), i = 1, . . . , 3q with some additional 3q vertices and 9q edges, in the following way. Let v1, v2, . . . , v3q be the additional vertices, where each vi corresponds to a set Ci of the instance I of X3C. Now, whenever there is a set Cp = {xi , xj , xk} in the instance I, add three edges linking vertex vp to the vertices ti,p, tj,p and tk,p of the gadgets H(xi), H(xj ), and H(xk), respectively. The vertices vj will be called v-vertices.we construct an instance I 0 = G = (V, E), w, Q of BCP such that: either I 0 has an optimal solution with measure w(V )/Q if I has an exact cover, or it has an optimal solution with measure 5 6w(V )/Q, if I does not have an exact cover. Let I = (X, C) be an instance of X3C, where C = {C1, C2, . . . , C3q} is a family of subsets of X = {x1, x2, . . . , x3q}. Let > 0 be a small number. Construct an instance I 0 = I 0 () = G = (V, E), w, Q of BCP .

Let G = (V, E) be a connected graph with a weight function w : V Z+ and let q 2 be a positive integer. For X V , let w(X) denote the sum of the weights of the vertices in X. We consider the following problem on G: find a q-partition P = (V1, V2, . . . , Vq) of V such that G[Vi] is connected (1 i q) and P maximizes min{w(Vi) : 1 i q}. This problem is called Max Balanced Connected q-Partition and is denoted by BCPq. We show that for q 2 the problem BCPq is NP-hard in the strong sense, even on q-connected graphs, and therefore does not admit a FPTAS, unless P = NP

q 3. We prove, by induction on q, that the problem DBCPq1 can be reduced to the problem DBCPq. Let I = (G, w, m) be an instance of DBCPq1 that consists of a (q 1)-connected graph G = (V, E), a function w : V Z+ and a positive integer m. The goal is to decide whether this instance has a solution with measure at least m. We construct an instance I 0 = (G0 , w0 , m) of DBCPq that consists of a q-connected graph G0 = (V 0 , E0 ), with V 0 = V {v 0}, where v 0 / V , and E0 = E {v 0u : u V }, and a function w 0 on the Balanced connected partitions of graphs 181 vertices of G0 such that: w 0 (v 0 ) = w(V )/(q 1) and w 0 (v) = w(v) for each v in V . It is obvious that G0 can be constructed in polynomial time in the size of I and G0 is q-connected. We claim that the instance I of DBCPq1 has a connected (q 1)-partition with measure at least m.