0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Is your graph simple, or do you allow multiple edges? For simple graphs, you always have such a partition for $m\ge 6$. $\endgroup$
    – domotorp
    Sep 17, 2023 at 4:14
  • $\begingroup$ Even if there exists such a partition, can you find it in polynomial time? additionally, for non-simple graphs, does it become NP-Hard? $\endgroup$
    – John
    Sep 17, 2023 at 6:44
  • $\begingroup$ Please reedit the question to make it more precise. $\endgroup$
    – domotorp
    Sep 17, 2023 at 8:02
  • $\begingroup$ 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? $\endgroup$
    – a3nm
    Sep 18, 2023 at 0:21
  • $\begingroup$ Yes, this is what I mean. Assume that there can be repetitions of the edges. $\endgroup$
    – John
    Sep 18, 2023 at 11:35

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Is there a known answer to the question you mentioned? does it imply NP-hardness/polynomial time algorithm for my problem? $\endgroup$
    – John
    Sep 17, 2023 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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