[Math] An edge partitioning problem on cubic graphs

algorithmsco.combinatoricscomputational complexitycomputer sciencegraph theory

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.

Best Answer

Thank you for the clarifications (the original post did not say each part should have size 3, maybe you can add that). I will take a stab, but it is not very clever so possibly I missed something.

Note,

  • for a given triple of edges, its subgraph has $\ge 3$ nodes with equality iff it is a triangle
  • thus for a given partition into $|E|/3$ triples, the sum of this over all parts is $\ge |E|$ with equality iff every triple forms a triangle.

However, it is known, due to Holyer 1981, that it's NP-complete to determine whether a graph can be edge-partitioned into triangles. So I think your problem is also NP-complete on these instances (taking $t=|E|$).

RE: your comment, thanks, I forgot it is cubic!

Related Question