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$
  • $\begingroup$ What do you mean by minimum cardinality partition? $\endgroup$ – droptop Aug 20 '20 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 '20 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 '20 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 '20 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 '20 at 15:07
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$
  • $\begingroup$ I see. So that's a reduction from vertex coloring, which means this must be NP-hard. $\endgroup$ – Jordan Aug 20 '20 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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