bigintegers's blog

By bigintegers, history, 4 weeks ago, In English,

Recently, I learned about Tarjan and Kosaraju's algorithms to find articulation points.

However, I was wondering whether there are algorithms to find vertices whose removal disconnects the graph into three or more components (as opposed to two). I've searched online, and I cannot find anything (perhaps I'm using the wrong search terms?).

I have a guess, but I'm not sure if this is correct. I think that we can take the DFS tree, and conclude that a vertex satisfies my condition if one of the following is true:

1) It's the parent of the DFS tree with three or more children.

2) It's not the parent of the DFS tree with two children.

This seems too easy to me, so I'm pretty sure it's wrong.

Can someone please help me with this problem?

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

»
4 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

This is NP-hard. I think there is a proof in this paper.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +27 Vote: I do not like it

    It's definitely not NP hard. The problem discussed in the paper is different from the one I am talking about.

    A brute force solution to my problem is to simply count the number of connected components, remove a vertex, perform DFS and count the components again.

    If the number of components increases by 2 or more, then the vertex satisfies my condition.

    This algorithm runs in polynomial time.

    However, I was wondering whether a non-bruteforce solution exists.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it -27 Vote: I do not like it

      Apparently, your question is not clear.

      Based on the brute force solution that you suggested, I think that you want to remove one vertex only. Based on your original post, it is not specified whether we could remove more than one vertex.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 5   Vote: I like it +6 Vote: I do not like it

        In the brute force solution, you remove vertices one at a time (adding them back once you're done with them) to find the property.

        Here is a restatement of the problem. Maybe it will make things more precise..

        Let $$$G = (V, E)$$$ be our graph. I am looking to find a subset $$$S \subseteq V$$$ of vertices with the following property:

        1) For any vertex $$$v \in S$$$, the graph $$$H = G \setminus {v}$$$ obtained by removing $$$v$$$ in $$$G$$$ along with any edges previously incident to $$$v$$$ has at least two more connected components than $$$G$$$.

        2) The size of $$$S$$$ is maximal (i.e. there is no other set $$$S'$$$ satisfying property (1) with $$$|S'| > |S|$$$).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this post being downvoted? Just curious.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    i have the same questions about why do community down vote everything that is not interesting for them.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    just wow, some of community are just down voting the comments/blogs which they are not much interested in, or they just disagree with the authors opinion, called down forces, and then some others, are trying to stop poor authors to get mad of getting down voted and they up vote comments/blogs, they are known as up forces. As the result, some comments/blogs with 20 or even more down votes slowly come up and now they are not that much down voted any more. I checked it out and realized that if you say "why i am getting down voted?" or equivalent sentences, then the up forces start helping you against down forces, as it happened a lot in my/other's comments/blogs. Its all my guesses, maybe some of them are wrong, so don't down vote me if you think its wrong, just reply why you think it happens.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I think it's just suspicious if an unrated (=possibly alt) account posts a blog asking for help in a problem with no source. Probably, some associate it with trying to cheat.

      Also, when you read a downvoted blog, your mindset will be different. I think because of such prejudice people are more likely to downvote something that is already downvoted.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Yes you are right, the rule is

        $$$Downvotes$$$
        $$$Brings$$$
        $$$Downvoters$$$
»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

you are right, your solution is not right, its true for trees but not for graphs, for example a complete graph with 10 vertices, the parent of DFS tree has more than 3 children, but for sure its not what you wanted. the thing is that in your solution, you erased back edges.

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

    Thank you for the counterexample. I guess I'll keep thinking.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In a complete graph the DFS tree is a path.

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

      ow man xd you are right, but its still wrong as back edges doesn't make any sens in the solution

»
4 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

If I understand correctly: given a connected(!) graph $$$G = (V, E)$$$, you are looking for all vertices $$$v$$$ such that $$$G[V - {v}]$$$ has at least $$$3$$$ components, correct?

It seems sufficient to find the biconnected components instead, and output exactly those vertices that are part of at least three biconnected components (this is one of the definitions of an articulation point, see here).

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

    Thanks so much. This was really helpful.

    I've been reviewing, and I still cannot see how to find the biconected components of a graph. The algorithm listed on the Wikipedia page you sent appears to be the algorithm that I learned to find articulation points. From my understanding, these articulation points separate the graph into biconnected components.

    I'm trying to modify the pseudocode that's presented on the Wikipedia page that you sent in order to implement the algorithm, but I'm having trouble doing so.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can find biconnected components using the following pseudocode. We keep a global stack.

      function dfs (u):
          mark u as visited
          push u onto the stack
          for each vertex v among the neighbors of u:
              if v is not visited:
                  call dfs(v)
                  if there is no back-edge from the subtree of v passing over u:
                      create a new biconnected component C
                      while the top of the stack is not v:
                          pop the top of the stack and add it to C
                      pop v from the top of the stack and add it to C
                      add u to C (but don't try to remove it from the stack)
      

      I haven't tested this, so possibly there is some oversight. I can't come up with a good explanation, but I suggest playing it out on paper, it provides some insight.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Here's the correct criterion about the DFS tree.

Removal of $$$u$$$ results in at least three connected components if and only if:

  1. it is the parent of the DFS tree and has at least three children;

  2. it is not the parent of the DFS tree and has at least two children $$$v$$$ such that there is no back-edge from the subtree of $$$v$$$ that passes over $$$u$$$.

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

    Ye you are right, i come up with the same things, but the rest :

    First for every vertex $$$u$$$(not the root), find $$$hi_u$$$ the height of highest vertex $$$v$$$(including its parent) such that there exist an edge that connects $$$u$$$ to $$$v$$$.(can be done in our DFS)

    Secondly for every vertex $$$u$$$, find $$$top_u$$$, the maximum $$$hi_v$$$ over all $$$v$$$ in its subtree including $$$u$$$ itself.(can be done with a DP in our DFS, just update every vertex from its children and itself)

    Then for ever vertex $$$u$$$, for every $$$v$$$ in it's exact children, if at least two such $$$v$$$ exist such that $$$top_v == height_u$$$($$$top_v$$$ is always at least equal to $$$height_u$$$), then this vertex is $$$GOOD$$$, otherwise its not.

    Also we can solve the following problem with the same idea: We have a graph $$$G$$$, multiedges and loops included. We want to erase a vertex, what is the maximum number of components we can have?, or for every vertex find the number of components it makes if we erase it.