1
$\begingroup$

I was just wondering if there is an efficient algorithm that given a undirected graph G, finds all the sub-graphs whose size is k (or less)?

I searched around, and only found problems about finding the connected components. But I am interested in the smaller and more local connected sub-graphs.

To clarify, the graph of interest (road networks) has n vertices, and has a relatively low degree (4 to 10). I am interested in finding/enumerating all connected sub-graphs with size k(in terms of nodes), e.g. by listing the vertices of each. k is relatively small.

Improve this question
$\endgroup$
2
  • $\begingroup$ Also, are the subgraphs induced subgraphs, or can both edges and vertices be deleted? $\endgroup$
    – Laakeri
    Commented Jan 25, 2020 at 21:48
  • $\begingroup$ See my updated answer. $\endgroup$
    – D.W. ♦
    Commented Jan 28, 2020 at 17:26

2 Answers 2

Reset to default
3
$\begingroup$

There can be exponentially many such subgraphs, so any such algorithm will necessarily be slow.

To enumerate all of them, choose any number $i$ in the range $[1,k]$, choose any subset $S$ of $i$ of the vertices, discard all edges that have an endpoint not in $S$, choose any subset of the remaining edges, then check if the graph with vertex set $S$ and the chosen edge subset is connected; if not, discard the graph; if yes, output the subgraph. If you implement each "choose" with an for-loop that enumerates over all possibilities, this will enumerate over all graphs. There are standard ways to enumerate all subsets of a set.

You can make it a bit more efficient by choosing the edges in a particular order:

  • for each $i \in [1,k]$:
    • for each subset $S$ of exactly $i$ of the vertices: (*)
      • let $E_1 = \{(u,v) \in E : u \in S, v \in S\}$ and $T := \emptyset$.
      • for each $v \in S$:
        • let $E_2 = \{(u,v) \in E : u \in S\}$.
        • if $E_2$ is empty and $T$ has no edge incident on $V$, go to the next iteration of the loop marked (*).
        • if $E_2$ is non-empty:
          • choose a non-empty subset $E_3$ of $E_2$.
          • set $T := T \cup E_3$ and $E_1 := E_1 \setminus E_2$.
      • if the graph $(S,T)$ with vertex set $S$ and edge set $T$ is connected, output it

I don't know how to guarantee polynomial delay, but this might be fine for your particular application.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. What about small k's? Could you elaborate on the exponential complexity? I thought it was O(n^k). $\endgroup$
    – tinlyx
    Commented Jan 25, 2020 at 5:43
  • $\begingroup$ Enumeration algorithms with possibly exponential output can be analyzed with terms like "output polynomial", "incremental polynomial" and "polynomial delay". I think in this analysis like this would make much more sense, because there obviosly are graph classes where the output is significantly smaller than $O(n^k)$. $\endgroup$
    – Laakeri
    Commented Jan 25, 2020 at 14:50
  • $\begingroup$ @Laakeri, good point. See my updated answer for something that addresses the parameter choices in the question. If you have ideas how to make it polynomial delay in general, that'd be interesting! $\endgroup$
    – D.W. ♦
    Commented Jan 28, 2020 at 17:26
3
$\begingroup$

If you are still interested, this paper proposes an algorithm of complexity $\mathcal{O}(n(d-1)^{k})$, with $d$ the max degree of your graph. Good luck in understanding, these guys are crazy

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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