# Another edge partitioning problem on cubic graphs

This question was motivated by a closely related problem An edge partitioning problem on cubic graphs

Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$

Question: Is there a partition of $E$ into subgraphs isomorphic to $K_{1,2}$ and $K_{1,1}$ such that the sum of the orders of the corresponding subgraphs is exactly $k$ ?

Is this problem polynomial time solvable or is it $NP$-complete?

Edit: Changed input graph to at most cubic graphs to avoid triviality.

• Replacing K_1,2 by two K_1,1s increases the total order by one, so the problem is just finding the maximum, which you can do by Edmond's algorithm on the line graph. Oct 28, 2010 at 17:39
• I'm looking for a partition with exact sum of orders? I do not see how finding the maximum matching in the line graph would help. Notice that for a given $k$, the edge partition is not necessarily a maximum matching? Oct 28, 2010 at 18:22
• Could you describe what you are looking for, in the line graph? A partition of the vertices such that... Oct 28, 2010 at 18:39
• @Colin, The problem is not restricted to line graphs. I'm looking for an Edge partition with sum of orders exactly equal to $k$. Oct 28, 2010 at 18:54