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

0
votes

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: 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.

1
c++algorithmgraph
Did you try and use the search function? Mentioning what you did and where that got you is not bad - showing both is better. - greybeard
well, the example is already wrong a connected component in an undirected graph is defined as "a set of vertices, such that there exists a path from each vertex to each other in the component and no path to vertices that are not part of the connected component". Neither of your subgraphs satisfies this property. - Paul
@AdamSilenko I use the adjacency matrix to describe the graph. I edited my post and added my DFS function for finding the connected components. - MayTheTreeBeWithYou
It seems that the first step would be to remove the odd vertices from the graph altogether, yielding a smaller graph and simplifying the problem drastically. - A.S.H
Start by removing all of the odd-numbered vertices, and the edges that connect those vertices. Then find the minimum spanning forest using Kruskal's algorithm. This may help simplify the problem. (Worst case every node is even and there's only one tree in the forest. But that's still good to know.) - user3386109

1 Answers

0
votes

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.