30
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Question: is there a partition of $E$ into $|E|/3$ parts such that the sum of the orders of the (nonnecessarily connected) corresponding subgraphs is at most $t$? I don't really understand the question. You take a (not necessarily proper) 3-colouring of the edges of $G$, then look at the sum of the orders of the subgraphs defined by the colour classes. But what is the order of such a subgraph, if it isn't $n$? Do you mean the set of vertices incident to an edge of the colour? $\endgroup$
    – Andrew D. King
    Commented Oct 26, 2010 at 18:07
  • 7
    $\begingroup$ The order of the subgraph is the cardinality of its vertex set. As an example, $K_4$ can be (edge-)partitioned into a triangle and a star, whose orders add up to 3+4=7. $\endgroup$
    – Anthony Labarre
    Commented Oct 26, 2010 at 21:12
  • 1
    $\begingroup$ Note, it's an $|E|/3$-edge-colouring, not necessarily proper $\endgroup$
    – Dave Pritchard
    Commented Nov 2, 2010 at 9:07
  • 1
    $\begingroup$ Dave: no, I want exactly $|E|/3$ parts, each of size $3$, and none can be empty. I agree that the problem is not especially natural, my motivation is that it is a special case of another problem I'm interested in (mathoverflow.net/questions/13364/…), so hardness of the former would imply hardness of the latter. $\endgroup$
    – Anthony Labarre
    Commented Nov 2, 2010 at 12:21
  • 1
    $\begingroup$ @Anthony: What is a natural upper bound? Is being natural crucial? $\endgroup$
    – Hans-Peter Stricker
    Commented May 3, 2012 at 12:25

1 Answer 1

Reset to default
1
$\begingroup$

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!

Improve this answer
$\endgroup$
2
  • $\begingroup$ A cubic graph (and actually, any $k$-regular graph with $k$ odd) cannot be partitioned into triangles. I agree that intuition would suggest that maximizing the number of triangles would be the way to go, but the following counterexample will convince you otherwise: take the complement of a cycle of length 6 (wwwteo.informatik.uni-rostock.de/isgci/images/g_co-C6.gif). If you use both triangles, you get a solution of weight 12, while discarding one triangle gives you a solution of weight 11. $\endgroup$
    – Anthony Labarre
    Commented Nov 2, 2010 at 22:33
  • $\begingroup$ Thanks for pointing out the missing bit, I modified my question accordingly. $\endgroup$
    – Anthony Labarre
    Commented Nov 3, 2010 at 7:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .