# Minimum cardinality graph partition that removes specific edges

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!

• What do you mean by minimum cardinality partition? Aug 20, 2020 at 18:47
• 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 Aug 20, 2020 at 19:49
• 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?? Aug 21, 2020 at 14:20
• 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. Aug 21, 2020 at 16:49
• @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\}$.
– plop
Aug 22, 2020 at 15:07