An edge partitioning problem on cubic graphs

Question

Has the complexity of the following problem been studied?

---

Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$

Question: is there a partition of $E$ into $|E|/3$ parts of size $3$ such that the sum of the orders of the (nonnecessarily connected) corresponding subgraphs is at most $t$?

---

Related work I found quite a few papers in the literature that prove necessary and/or sufficient conditions for the existence of a partition into some graphs containing three edges, which is somehow related, and some others on computational complexity matters of problems that intersect with the above (e.g. the partition must yield subgraphs isomorphic to $K_{1,3}$ or $P_4$, and no weight is associated with a given partition), but none of them dealt exactly with the above problem.

Listing all those papers here would be a bit tedious, but most of them either cite or are cited by Dor and Tarsi.

20101024: I found this paper by Goldschmidt et al., who prove that the problem of edge partitioning a graph into parts containing AT MOST $k$ edges, in such a way that the sum of the orders of the induced subgraphs is at most $t$, is NP-complete, even when $k=3$. Is it obvious that the problem remains NP-complete on cubic graphs, when we require strict equality w.r.t. $k$?

Additional information

I've tried some strategies that failed. More precisely, I found some counterexamples that prove that:

• maximising the number of triangles does not lead to an optimal solution; which I find somehow counter-intuitive, since triangles are those subgraphs with lowest order among all possible graphs on three edges;

• partitioning the graph into connected components does not necessarily lead to an optimal solution either. The reason why it seemed promising may be less obvious, but in many cases one can see that swapping edges so as to connect a given subgraph leads to a solution with smaller weight (example: try that on a triangle with one additional edge connected to each vertex; the triangle is one part, the rest is a second, with total weight 3+6=9. Then exchanging two edges gives a path and a star, with total weight 4+4=8.)

Answer 1

Here is a suggestion for how to show it's NP hard. I don't know if this works or not. First, consider the same problem on multigraphs. NP hardness may be easier to prove there. Try reducing from cubic MAX CUT which is NP hard even to approximate (Berman and Karpinski "On Some Tighter Inapproximability Results"). Divide each edge into two and at each of the new degree-2 vertices attach a vertex with self-loop. Does your maximum partition correspond to a maximum cut?

--

Here is a bit more explanation.

(1) The problem of maximizing (number of sources+number of sinks) over all orientations of a cubic graph is related to MAXCUT by some linear function. This requires showing some corersspondence between maximal cuts and sources-and-sinks-maximal orientations. In one direction, in a maximum cut (U,V), we can orient all edge from U to V. The internal edges E(U) form a matching, so these can be oriented arbitrarily and similarly for E(V), and the total number of sources and sinks is some linear function of the size of the cut. In the other direction, given a sources-and-sinks-maximal orientation, the partition U=vertices of in-degree 0 or 1, V=vertices of in-degree 2 or 3 gives a cut.

(2) In the edge-bisecting transformation I described above, in an optimal configuration each loop is coloured the same as the edge next to it, and w.l.o.g that edge is coloured the same as the some other (non-loop) edge next to that. So each bisected edge has one colour coming from its attached loop and one other colour. This corresponds to an orientation and (1) applies.