Is this edge-partitioning NP-Hard?

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

• Is your graph simple, or do you allow multiple edges? For simple graphs, you always have such a partition for $m\ge 6$. Commented Sep 17, 2023 at 4:14
• 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
Commented Sep 17, 2023 at 6:44
• Please reedit the question to make it more precise. Commented Sep 17, 2023 at 8:02
• 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?
– a3nm
Commented Sep 18, 2023 at 0:21
• Yes, this is what I mean. Assume that there can be repetitions of the edges.
– John
Commented Sep 18, 2023 at 11:35