Instance: G = (V, E) a graph and k ∈ N ∗ .
Question: Is there a partition of V of cardinality k, V1, V2, . . . , Vk such that each Vi induces a connected subgraph (i. e., [Vi ]G is connected for each i = 1, k)?
Describe an algorithm of time complexity O(|V | + |E|) that solves this problem (hence, CPARTITION ∈ P ).
Compute the connected components by depth-first search. Let k' be the number of components. The answer is "yes" if and only if k'
Compute the connected components by depth-first search. Let k' be the number of components. The answer is "yes" if and only if k'
You can use a BFS or DFS for compute the connected components of the graph in O(|V| + |E|). Then as Adam said if the number of connected componets is lower tha or equal than k and clearly the number of vertices in the graph is greater or equal than k, then the answer is yes.
Hope the following link is of a good use
https://wwwhome.ewi.utwente.nl/~stillgj/conopt/pvsnp.pdf
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs