# 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? – droptop Aug 20 '20 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 – Jordan Aug 20 '20 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?? – droptop Aug 21 '20 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. – Jordan Aug 21 '20 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 '20 at 15:07