MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 82 characters in body

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!

2 added 23 characters in body

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

1

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