Hello everyone,

I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that the sets of users of both places form a large intersection.

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.

A more closely related work is 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$. Another difference between their problem and the one I describe is that they do not allow subgraphs to be disconnected. Is it obvious that their problem remains NP-complete on cubic graphs, when we require strict equality w.r.t. $t$ and drop the connectivity constraint?

**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.)

I'm currently trying to work out reductions from related problems (see above), as well as other leads suggested by the kind readers of the TCS forum.

naturalupper bound? Is being natural crucial? $\endgroup$ – Hans-Peter Stricker May 3 '12 at 12:25