nor's blog

Traversing the complement graph in linear/near-linear time in multiple ways
By nor, 3 years ago, In English

https://nor-blog.codeberg.page/posts/2021-08-12-complement-graph-traversal/

  • Vote: I like it
  • +168
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +44 Vote: I do not like it

NORZ

→ Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Just gonna pretend that i understand this stuff

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When this type of formulation work? is this for this particular question or if you have some more problem Please Share. Thanks for explaining

→ Reply
»
9 months ago, # |
  Vote: I like it +23 Vote: I do not like it

I just realized that there is also beautiful a linear-time solution to DFS, working in provable $$$O(n + m)$$$ time, using doubly-linked lists and an idea similar to "dancing links".

The main idea is to store the "global visited list" as a doubly linked list. After you call dfs(child), you get back to the next value by going through the prev pointers in the linked list.

It is important that the "deletion" from the linked list does not re-link the deleted node (let it point to the old prev and next nodes). You can prove intuitively that the "invalid" list you are traversing from this deleted node is at any time a superset of the real "valid" list. Also, because we use the prev pointers to go from an invalid (visited) node to a valid (unvisited) node, then these operations amortize beautifully (just like the principle of a stack).

Implementation: 219699489 (I tried to make it as similar as possible to the original DSU implementation for ease of comparison)

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for the implementation! As a consequence, we can find the DFS tree of the complement graph in linear time, which means we can find 2-vertex-connected and 2-edge-connected components (and hence, the block-cut tree and the bridge tree respectively) of an arbitrary undirected graph in the same time complexity.

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

One of my favorite implementation of the "complement traversal" problem is as follows.

The problem becomes trivial if $$$n \leq \sqrt{m}$$$ because the simple $$$O(n^2)$$$ algorithm wins. Otherwise suppose that $$$0$$$ is the vertex with the minimum degree among the graph $$$G$$$. Hence $$$\mathrm{deg}(0) \leq \frac{2m}{n} = O(\sqrt{m})$$$. Let $$$X = V \setminus \{0\} \setminus N(0)$$$. i.e., those vertices which are not adjacent to the vertex $$$0$$$ in $$$G$$$. $$$X \cup \{0\}$$$ should be connected in $$$\bar{G}$$$. Brute force on $$$N_0$$$ gives an $$$O((\frac{2m}{n})^2) = O(m)$$$ algo.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This algorithm is indeed really cool. I remember reading about it in this comment at some point but seemed to have forgotten it over time, so thanks for the reminder!

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does $$$V$$$ and $$$N$$$ mean in $$$V∩N(u_1)∩⋯∩N(u_i)⊆N(u_i)$$$?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    $$$V$$$ is the set of all vertices of the graph, and $$$N(u)$$$ denotes the set of neighbours of a vertex $$$u$$$.

    → Reply
»
5 weeks ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

In the naive DFS solution, won't there be O(n) skips per vertex which in worst case might lead to O(n * n) skips ?

In the following graph
1: 2 3 4 5 ..... n-1
.
.
.
n-2: 2 3 4 ... n-4
n-1: 2 3 4 .... n-3
n: 2 3 4 5 .... n-2

When starting dfs from 1, we will skip all the vertices from 2 to n-1 and make a recursive call to dfs(n). dfs(n) will skip all the vertices from 2 to n — 2 again and will make a recursive call to dfs(n-1) and so on. This way, won't we make a total of O(n * n) skips ?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    You can get a better bound here. Note that whenever you skip a vertex $$$v$$$ while in the DFS for vertex $$$u$$$, it is because $$$(u, v)$$$ is not an edge in the complement graph. This is the same as saying that $$$(u, v)$$$ is an edge in the input graph. So the total number of skips can be at most double the number of edges in the input graph, which is $$$m$$$.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The graph I mentioned in the edit should have O(n * n) skips, right? Also m is of the order O(n * n) in that test case so we can say there are O(m) skips. But since m is bounded by min(n * (n + 1) / 2, 200000)), we won't be getting such test case for large value of n.

      Am i right or missing something ?

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Yes, it will take $$$O(m)$$$ skips regardless of what your graph is. In this case, $$$m = O(n^2)$$$, so it does not contradict what you said.

        → Reply