0
$\begingroup$

There seems to be various implementations of algorithms that find the connected components of a graph.

I have not found, however, an algorithm or implementation for finding which of the connected components are also complete. Does anybody know of one?

Thank you!

$\endgroup$
  • 4
    $\begingroup$ You don't need a special algorithm. Given a connected component, just check that all the edges are there. $\endgroup$ – Yuval Filmus Jun 25 '17 at 2:09
  • 1
    $\begingroup$ Implementations are off-topic here. $\endgroup$ – Yuval Filmus Jun 25 '17 at 2:09
0
$\begingroup$

Most graph libraries will find the connected components of a graph G as a list of connected subgraphs [H1, H2, H3, ...] and most of these libraries will have the functionality to obtain the number of nodes and number of edges in a graph. Assuming H is a simple graph (no loops, no multiple edges) with m edges and n vertices, one can say it is complete if

m == n*(n-1)/2

So, given the output of connected components, you should do:

for each graph H in [H1, H2, ...]
  int n = H.getNumVertices()
  int m = H.getNumEdges()
  if (n*(n-1) == 2*m)
    state that H is complete
  else
    state that H is not complete
$\endgroup$
  • $\begingroup$ It should be noted that the equality is valid only for simple graphs (no loops, no multiple edges) . $\endgroup$ – anr Jun 28 '17 at 21:28
0
$\begingroup$

Though the answer is already posted, here I propose a beatiful approach. One can notice that a graph is union of cliques if and only if it doesn't contain a path on 3 vertices, $P_3$, as induced subgraph. It looks like a triangle without one side. Just checking the adjacency matrix for $a_{ij}+a_{ik}+a_{jk}=2$ will be sufficient. It's $O(n^3)$.

$\endgroup$
  • $\begingroup$ I don't think the OP wants to decide if all components are cliques. they want to obtain all clique-components. $\endgroup$ – Raphael Jun 29 '17 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.