YahiaSherif's blog

How do I get a 2-3 subgraph or 3-4 subgraph? (Research question)
By YahiaSherif, history, 2 years ago, In English

Hi, I am writing my bachelor thesis and I came across a study which mentions finding a 2-3 subgraph and a 2-4 subgraph of an undirected graph as one of its subtask but it doesn't mention an algorithm to do it but it just says that it is done using DFS.

I couldn't really find anything useful online solving these problems.

A 2-3 subgraph is a subgraph where each node has degree 2 or 3 in this subgraph (we remove edges which go to nodes outside the subgraph) and our task is to find a maximal 2-3 subgraph (it doesn't have to be maxmimum in terms of size just that we can't add another node to it). A 2-4 subgraph is just the same but with 2, 3 and 4.

Can anyone help by describing an algorithm or linking an article/paper?

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YahiaSherif (previous revision, new revision, compare).

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

For 2-3 you could go like this. Start from any induced cycle, which is a 2-subgraph (there are at least a couple of ways to find one), so in particular it is a 2-3 subgraph as well. Then you can try adding vertices outside of it to it until you can't add anything else. I believe everything could be done in linear time, but I did not think of all the details.

For a 3-4 subgraph you can deal with the maximality part in the same way, but you would need to find any 3-4 subgraph to start with. For that I don't have a good quick idea yet. In particular, you will find 2-3 subgraph in any graph that is not a forest, but characterisation of graphs that have 3-4 subgraphs is probably not obvious?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, I had the same general idea of starting with a cycle and so. but the challenge was when adding nodes I can't nodes one by one as it may end up in situation where a node with degree 1 is in the subgraph which is not allowed. The alternative was to try and connect 2 nodes which already have degree 2 with a path which is not in the subgraph completely but I get the feeling that this solution is not complete.

    Sorry I made a mistake about the second one, it is 2-4 subgraph which means 2,3,4 are allowed.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Also it will not be linear as in the way I suggested because I would have to dfs from each node with degree 2 I think

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

        In order to find an induced cycle? Not really. Let's compute DFS tree from any vertex and take the shortest edge which does not belong to DFS tree. Shortest meaning between vertices with the smallest difference of their depths. It will create an induced cycle along with the path between them in the tree. You can find one in a bit different way by inspecting BFS tree as well

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

          I meant adding nodes to the subgraph. It isn't linear in the way I suggested.

          → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I am not really sure what is the issue with the part ensuring the maximality. If a node has degree one, it couldn't be added to our subgraph in the first place. It could be the case that a node outside couldn't be added, but after some time can be added (because its degree to already included vertices rose from 0 or 1 to 2 or 3), but that is not any problem if you do it in the following way:

      while(can add some vertex) { add one }

      which can be expressed in a more elaborated way

      for (int iter = 1; iter <= n; iter++) {
  for (int v = 1; v <= n; v++) {
    if (v can be added) {
      add(v);
    }
  }
}

      When expressed this way, it will be too slow, but you should be able to optimize it by tracking for each vertex its current degree to already included vertices and whether it has an included neighbor with degree 3 (which will prevent adding the vertex itself).

      And if we are talking about 2-4 subgraph and not 3-4 subgraphs then it is easy. The only difference will be tracking whether you have an included neighbor with degree 4 instead of 3

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

        Check this example:

        Graph has 6 nodes.

        Edges: 1-2, 1-3, 2-3, 2-4, 4-5, 3-5, 2-6

        Assume the first cycle we find is 1-2-3. Then when we try to add new nodes we add node 6 to the subgraph. Now node 2 already has 3 edges in the subgraph, so we can't add node 4 but we add node 5. So now our subgraph is 1, 2, 3, 5, 6 which has nodes 5,6, having degree 1 in the subgraph.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Why do you add 6 if it has degree 1 :|? 1,2,3,6 is not a 2-3 subgraph. 1,2,3 is already a maximal 2-3 subgraph, you can't add anybody to it.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I can add 4 and 5 to 1-2-3 and it would still be a 2-3 subgraph. Also if for example we had a node 7 which was connected to 6 then 6 would have degree 2 in the original graph.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Ouch, sorry. Forget everything I said about maximality :(.

              As an excuse I could say that in majority of cases when maximality is considered, families of good sets are hereditary (i.e. if A is good then each subset of A is good as well) and then you can ensure maximality by adding elements one by one, while here our property is not hereditary and we cannot add neither 4 not 5 on their own, but adding them both works. Moreover, your wording was misleading as well as you have defined maximality as "we cannot add another node to it" :P. I know what maximality means, but that already set me on the wrong track I was familiar with xD

              → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YahiaSherif (previous revision, new revision, compare).

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

Let's call the graph $$$G$$$. Start with any 2-3 subgraph $$$H$$$ in $$$G$$$, and then do the following repeatedly while you can:

  • Delete all the edges in $$$G$$$ but not in $$$H$$$ that are incident to a node with degree 3 in $$$H$$$ as those edges can not be added to $$$H$$$.
  • Delete all nodes in $$$G$$$ with degree $$$1$$$ (repeatedly).
  • Pick a node with degree $$$2$$$ in $$$H$$$, and start DFS in $$$G$$$ from there until you reach a node in $$$H$$$ or you reach a node that you visited before in the DFS itself. Don't consider any edge that is already in $$$H$$$ in the DFS. Add that path you found to $$$H$$$.

This should find a maximal 2-3 subgraph in linear time in the number of edges. The case for 2-4 is very similar to this too.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Very interesting, thank you! Do you know if this was published before, if so where so I that I can reference it in my thesis?

    → Reply