2
$\begingroup$

I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for an algorithm.

Input: A connected, undirected graph G = (V, E) in which certain edges are labelled "bad".

Output: The minimum cardinality partition of V such that 1) all of the induced subgraphs of the partition are connected, and 2) none of the induced subgraphs contains a bad edge.

Thanks!

$\endgroup$
5
  • $\begingroup$ What do you mean by minimum cardinality partition? $\endgroup$
    – droptop
    Aug 20, 2020 at 18:47
  • $\begingroup$ What I mean is a partition of the vertices into non-overlapping sets that meet conditions 1) and 2) with the smallest possible number of sets $\endgroup$
    – Jordan
    Aug 20, 2020 at 19:49
  • $\begingroup$ I don't still get it. If all the bad edges are removed, then isn't the number of connected components in the resulting forest the number of partitions?? $\endgroup$
    – droptop
    Aug 21, 2020 at 14:20
  • $\begingroup$ The number of connected components will be equal to the size of the partition, yes. However, I don't see where you would get a forest in this process. Also, you can't just remove the bad edges freely. The only way to get rid of bad edge is to ensure that it bridges two sets in the partition, in which case it isn't included in any induced subgraph. $\endgroup$
    – Jordan
    Aug 21, 2020 at 16:49
  • $\begingroup$ @droptop Consider the graph $G=(V,E)$ given by $V=\{a,b,c\}$, $E=\{\{a,b\},\{a,c\},\{b,c\}\}$ and $\{b,c\}$ the only bad edge. If we remove $\{b,c\}$ the graph remains connected. But is we take $\{a,b,c\}$ as the only element of the partition, the induced graph on $G$ by these vertices contains the edge $\{b,c\}$. We need to break further this connected (with non-bad edges) component to satisfy condition (2). For example as $\{a,b\}$ and $\{c\}$. $\endgroup$
    – plop
    Aug 22, 2020 at 15:07

1 Answer 1

1
$\begingroup$

Try to look at what happens when all the edges are bad edges.

What would the question be if I asked:

Can you partition the graph into three partitions, e.g. red, green, blue, such that for every edge, the "color" of the endpoints of each edge is "chromatic".

(Let's also make the graph into a complete graph by adding "good" edges between every non-adjacent vertices.)

$\endgroup$
1
  • $\begingroup$ I see. So that's a reduction from vertex coloring, which means this must be NP-hard. $\endgroup$
    – Jordan
    Aug 20, 2020 at 23:51

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.