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.

$\endgroup$
  • 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 '10 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 '10 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 '10 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 '10 at 18:54
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.

$\endgroup$
  • 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 '10 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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