The connected components in an undirected graph of a given amount of vertices (algorithm)

Question

I want to solve a problem where is given an undirected graph and its vertices, a value k, where k is the number of vertices that should be in each connected component, and I have to find all connected components of the given graph which has only even numbers vertices. I have to find out how many such connected components are there and save the value of each vertices from each connected components.

Example: K=3 and we are given the following graph:

For that graph we have 2 connected components where all vertices are even numbers. The first connected component is made of the following vertices : 8, 2, 4; and the 2nd connected component is made of the following vertices : 2, 4, 6.

Is there an algorithm for finding the connected components in an undirected graph of a given amount of vertices? Or can anyone help me with an idea on how I should approach the problem? I've tried doing it with the DFS algorithm but I ended up nowhere.

Answer 1

Brute force:

Break the problem into two sub-problems:

1) Identify all connected components (CC) that contain all even numbers, and of arbitrary size. In the example you gave above, there would be only one CC: (8,2,4,6). This can be done in O(e+n) time, where e is the number of edges and n the number of nodes using BFS or DFS. (This is the fast step.)

2) Within each CC from step 1) enumerate all connected subgraphs of size k. This is the slow part. The brute force solution for a CC of size m nodes is O( k* (m choose k)) = O(k m^k) by enumerate all m choose k possible k nodes from m and using k operations to determine if they are connected.

Given that (1) is fast and (2) is slow you are probably not understanding the problem well enough to know how to circumvent the need to compute (2). There may be a faster way to compute (2), what I suggested is probably as close as posisble to brute-force.