<p>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.</p>

CC BY-SA 4.0
2024-01-24T20:56:05.337Z
is there any reason why such an algorithm shouldn't be possible on arbitrary graphs (not just cubic graphs)?
Antoine Amarilli 'a3nm'
CC BY-SA 2.5
2010-10-29T19:22:09.010Z
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
CC BY-SA 2.5
2010-10-28T19:34:33.173Z
2010-10-28T19:34:33.173Z
Marek Chrobak
<p>This question was motivated by a closely related problem 
<a href="https://cstheory.stackexchange.com/questions/2307/an-edge-partitioning-problem-on-cubic-graphs.">An edge partitioning problem on cubic graphs</a>
<a href="https://cstheory.stackexchange.com/questions/2307/an-edge-partitioning-problem-on-cubic-graphs"></a></p>

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

<p>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$ ?</p>

<blockquote>
  <p>Is this problem polynomial time solvable or is it $NP$-complete?</p>
</blockquote>

<p><strong>Edit:</strong> Changed input graph to at most cubic graphs to avoid triviality.</p>

CC BY-SA 2.5
2010-10-28T17:39:32.187Z
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
CC BY-SA 2.5
2010-10-28T18:22:03.600Z
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
CC BY-SA 2.5
2010-10-28T18:39:58.180Z
Could you describe what you are looking for, in the line graph? A partition of the vertices such that...
Colin McQuillan
CC BY-SA 2.5
2010-10-28T18:54:00.517Z
@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
<cc.complexity-theory><graph-theory><np-hardness>
Another edge partitioning problem on cubic graphs
Mohammad Al-Turkistany
# Another edge partitioning problem on cubic graphs

(Asked by: username_0 on 2010-10-28)

This question was motivated by a closely related problem
[An edge partitioning problem on cubic graphs](https://cstheory.stackexchange.com/questions/2307/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.

**Tags:** cc.complexity-theory, graph-theory, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: Could you describe what you are looking for, in the line graph? A partition of the vertices such that...  
> **username_0**: @Colin, The problem is not restricted to line graphs. I'm looking for an Edge partition with sum of orders **exactly** equal to $k$.  

---

## 1 answers

### Answer by username_2 on 2010-10-28. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  
> **username_3**: is there any reason why such an algorithm shouldn't be possible on arbitrary graphs (not just cubic graphs)?  

---

