Revisions - MathOverflow

Return to Answer

added 82 characters in body

view source

edited Nov 2 2010 at 23:43

Thank you for the clarifications (the original post did not say each part should have size 3)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!

added 23 characters in body

view source

edited Nov 2 2010 at 21:05

Dave Pritchard
677●5●12

Thank you for the clarifications (the original post did not say each part should have size 3). 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 it I think your problem is also NP-complete on these instances (taking $t=|E|$).

view source

answered Nov 2 2010 at 20:56

Dave Pritchard
677●5●12

Thank you for the clarifications (the original post did not say each part should have size 3). 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 it is NP-complete on these instances (taking $t=|E|$).