I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only connected to each other and A and F (don't have to be fully connected). Is there a name for this? And is there an algorithm for finding such subgraphs? The distance of A and F is defined by their shortest path: for example, if d=4, I would want to find all subgraphs where the shortest path between A-like and F-like nodes is at most 4.

  • 1
    $\begingroup$ Welcome to COMPUTER SCIENCE @SE. If "the naming" is important to you, consider tagging terminology. (induced components?) $\endgroup$
    – greybeard
    Oct 12 '20 at 11:15

I don't know if there's a name for such subgraphs, but here's something to get you started.

If you require the subgraphs to be connected

A polytime algorithm for $G=(V,E)$ would be: for every possible unordered pair $(A,F)\in \binom{V}{2}$ consider the connected components of the graph induced by $V\smallsetminus\{A,F\}$. Then consider the classes which contain at least a neighbour of $A$ and one of $F$ (this step is required if the original graph was not connected). Then for each subgraph you found you can "add $A$ and $F$ back in" and look for their distance in the graph.

Let's sketch correctness (only the step about the subgraphs we are looking for being the connected components needs to be verified).

  • All components are solutions: by construction they only share links with themselves and A and F, and are connected.
  • All solutions are components: they are connected and only connect to the rest of the graph through A and F.

I am guessing you can do much better in runtime, but your problem seems to be in $P$ at least.

If you don't

You need to also consider combinations of the subgraphs found above, but in terms of the minimum distance it doesn't change much.


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.