CODEWITHSUNDEEP
algorithmtime-complexitygraph-algorithm
Psychonaut
Psychonaut

Reputation: 897

Efficiently find connected subgraphs (not necessarily induced) of a given order

Given a connected undirected vertex-labelled graph, an edge in the graph, and some number n ≥ 2, is there an efficient algorithm to find all the connected (but not necessarily induced) subgraphs of order n that contain that edge?

I thought the obvious thing to do would be a sort of recursive traversal of the edges, starting from the given edge and taking care that no one path uses an edge more than once (though visiting the same vertex multiple times is permitted). After traversing each edge I check how many vertices are on the path. If it's less than n, I proceed with the traversal. If it's equal to n, I yield the subgraph corresponding to the path and proceed with the traversal. If it's greater than n, I stop. However, this method is inefficient as it produces many of the same subgraphs over and over.

(If it matters, all vertices in the original graph are of degree 8, and I will be looking for subgraph orders up to 15.)

Upvotes: 1

Views: 639

Answers (1)

Psychonaut
Psychonaut

Reputation: 897

David Eisenstat's comment to my question suggested adapting his answer to a similar question. The following pseudocode is that adaptation, which I've verified works and doesn't generate any one subgraph more than once. In it n refers to the order of the subgraphs to be returned (the test for which can be omitted if you want to return all subgraphs) and neighbours(e) means the set of edges which share an endpoint with e. When the function is first called, the subgraphEdges parameter should contain the given edge, and the rest of the parameters should be set accordingly.

GenerateConnectedSubgraphs(edgesToConsider,
                           subgraphVertices,
                           subgraphEdges,
                           neighbouringEdges):
    let edgeCandidates ← edgesToConsider ∩ neighbouringEdges
    if edgeCandidates = ∅
        if |subgraphVertices| = n
           yield (subgraphVertices, subgraphEdges)
    else
        choose some e ∈ edgeCandidates
        GenerateConnectedSubgraphs(edgesToConsider ∖ {e},
                                   subgraphVertices,
                                   subgraphEdges,
                                   neighbouringEdges)
        GenerateConnectedSubgraphs(edgesToConsider ∖ {e},
                                   subgraphVertices ∪ endpoints(e),
                                   subgraphEdges ∪ {e},
                                   neighbouringEdges ∪ neighbours(e))

Upvotes: 1

Related Questions