1

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.

Community
  • 1
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 2
    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. – Colin McQuillan Oct 28 '10 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? – Mohammad Al-Turkistany Oct 28 '10 at 18:22
  • Could you describe what you are looking for, in the line graph? A partition of the vertices such that... – Colin McQuillan Oct 28 '10 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$. – Mohammad Al-Turkistany Oct 28 '10 at 18:54

1 Answers1

3

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.

Marek Chrobak
  • 249
  • 3
  • 6
  • 1
    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. – Marek Chrobak Oct 29 '10 at 19:22
  • is there any reason why such an algorithm shouldn't be possible on arbitrary graphs (not just cubic graphs)? – a3nm Jan 24 '24 at 20:56