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

Improve this question
$\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 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 at 6:44
  • $\begingroup$ Please reedit the question to make it more precise. $\endgroup$
    – domotorp
    Sep 17 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 at 0:21
  • $\begingroup$ Yes, this is what I mean. Assume that there can be repetitions of the edges. $\endgroup$
    – John
    Sep 18 at 11:35

1 Answer 1

Reset to default
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?

Improve this answer
$\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 at 6:45

Your Answer

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

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