# An edge partitioning problem on cubic graphs

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$?

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

• What is the order of a subgraph? – Mohammad Al-Turkistany Oct 19 '10 at 16:01
• The cardinality of its vertex set. – Anthony Labarre Oct 19 '10 at 16:22
• Perhaps looking at the case where the graph is also planar might give some insight into the more general case? – Joseph Malkevitch Oct 20 '10 at 15:58
• Thanks, I hadn't thought of that. I'll try and see whether it helps. – Anthony Labarre Oct 21 '10 at 5:47
• I was wondering whether strategies like those described in the “additional information” section would work or not. It is great that you added that part! – Tsuyoshi Ito Oct 22 '10 at 0:00