1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Colin McQuillan
    Oct 28, 2010 at 17:39
  • $\begingroup$ 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? $\endgroup$
    – Mohammad Al-Turkistany
    Oct 28, 2010 at 18:22
  • $\begingroup$ Could you describe what you are looking for, in the line graph? A partition of the vertices such that... $\endgroup$
    – Colin McQuillan
    Oct 28, 2010 at 18:39
  • $\begingroup$ @Colin, The problem is not restricted to line graphs. I'm looking for an Edge partition with sum of orders exactly equal to $k$. $\endgroup$
    – Mohammad Al-Turkistany
    Oct 28, 2010 at 18:54

1 Answer 1

Reset to default
3
$\begingroup$

Perhaps I don't understand the question, but the way I interpret it, Colin's answer seems correct. It is enough to find the minimum possible k for which such partition exists, say k_0. (This is a partition with maximum number of K_21's.) There is a partition for any k between k_0 and 3n/2, because splitting K_21 into two K_11's increases the sum of cardinalities by 1. The K_21's in your partition induce a matching in the line graph of G, so this k_0 corresponds to the maximum matching in the line graph, and this matching can be found in polynomial time.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hmm. What am I missing? This algorithm does not use regularity of G. Finding max matching in the line graph G will work for any graph G, as far as I can tell. $\endgroup$
    – Marek Chrobak
    Oct 29, 2010 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.