<p>This question boils down to answering to simpler questions.</p>
<p>Can you find a graph with 6 edges where it is impossible to partition the edges?</p>
<p>In a graph of more than 6 edges can you always find a triple of edges that is not a forest?</p>

CC BY-SA 4.0
2023-09-17T06:45:57.717Z
Is there a known answer to the question you mentioned? does it imply NP-hardness/polynomial time algorithm for my problem?
John
CC BY-SA 4.0
2023-09-16T20:43:58.153Z
2023-09-16T20:43:58.153Z
Martin Vatshelle
<p>Let <span class="math-container">$G = (V,E)$</span> be an undirected graph with <span class="math-container">$m = |E|$</span> edges (assume that <span class="math-container">$m = 3t$</span> for some <span class="math-container">$t \in \mathbb{N}$</span>).</p>
<p><strong>Problem:</strong> Partition <span class="math-container">$E$</span> to <span class="math-container">$q = \frac{m}{3}$</span> sets <span class="math-container">$S_1,S_2,\ldots, S_q \subseteq E$</span> sets such that for each <span class="math-container">$i \in \{1,2,\ldots,q\}$</span>  it holds that (1) <span class="math-container">$|S_i| = 3$</span> and (2) <span class="math-container">$S_i$</span> induces a forest (graph with no cycles) in <span class="math-container">$G$</span>.</p>
<p><strong>Question:</strong> Is the above problem NP-Hard for a general graph <span class="math-container">$G$</span>?</p>

CC BY-SA 4.0
2023-09-17T04:14:59.473Z
Is your graph simple, or do you allow multiple edges? For simple graphs, you always have such a partition for $m\ge 6$.
domotorp
CC BY-SA 4.0
2023-09-17T06:44:23.057Z
Even if there exists such a partition, can you find it in polynomial time? additionally, for non-simple graphs, does it become NP-Hard?
John
CC BY-SA 4.0
2023-09-17T08:02:09.690Z
Please reedit the question to make it more precise.
domotorp
CC BY-SA 4.0
2023-09-18T00:21:33.717Z
I'm not sure I understand the problem. When you say a set $S_i$ "induces a forest", knowing that $|S_i| = 3$, do you just mean that the three edges of $S_i$ should not form a triangle?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-09-18T11:35:03.667Z
Yes, this is what I mean. Assume that there can be repetitions of the edges.
John
<graph-algorithms><np-hardness><partition-problem>
Is this edge-partitioning NP-Hard?
John
# Is this edge-partitioning NP-Hard?

(Asked by: username_0 on 2023-09-16)

Let $G = (V,E)$ be an undirected graph with $m = |E|$ edges (assume that $m = 3t$ for some $t \in \mathbb{N}$).

**Problem:** Partition $E$ to $q = \frac{m}{3}$ sets $S\_1,S\_2,\ldots, S\_q \subseteq E$ sets such that for each $i \in \{1,2,\ldots,q\}$ it holds that (1) $|S\_i| = 3$ and (2) $S\_i$ induces a forest (graph with no cycles) in $G$.

**Question:** Is the above problem NP-Hard for a general graph $G$?

**Tags:** graph-algorithms, np-hardness, partition-problem

> **Comments:**
> **username_1**: Is your graph simple, or do you allow multiple edges? For simple graphs, you always have such a partition for $m\ge 6$.  
> **username_0**: Even if there exists such a partition, can you find it in polynomial time? additionally, for non-simple graphs, does it become NP-Hard?  
> **username_1**: Please reedit the question to make it more precise.  
> **username_2**: I'm not sure I understand the problem. When you say a set $S_i$ "induces a forest", knowing that $|S_i| = 3$, do you just mean that the three edges of $S_i$ should not form a triangle?  
> **username_0**: Yes, this is what I mean. Assume that there can be repetitions of the edges.  

---

## 1 answers

### Answer by username_3 on 2023-09-16. Score: 1

This question boils down to answering to simpler questions.

Can you find a graph with 6 edges where it is impossible to partition the edges?

In a graph of more than 6 edges can you always find a triple of edges that is not a forest?

> **Comments:**
> **username_0**: Is there a known answer to the question you mentioned? does it imply NP-hardness/polynomial time algorithm for my problem?  

---

