4
$\begingroup$

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to compute a maximal 2-3 subgraph of the input graph.

To be precise, a 2-3 graph is one that has only vertices of degree either 2 or 3. By maximal we mean that there is no other 2-3 subgraph which contains the maximal subgraph as a proper subgraph. It does not have to be a maximum subgraph.

The authors of the paper claim that the computation can be carried out by a simple Depth First Search (DFS) on the graph. However, this algorithm seems to elude me. How can the maximal subgraph be computed?

|cite|improve this question
$\endgroup$
0
$\begingroup$

Basically, in 2-3 graph, the lower bound 2 means that any node has to be in a cycle.

In DFS, when you reach an already visited node, you found a cycle. Just check if adding this cycle to your subgraph also respect the upper bound 3.

As you suggested, the maximal 2-3 subgraph is not unique. But if you built it following this method, you ensure that any node/vertex of $G$ you did not select in your subgraph:

  • either is not part of any cycle and would lead to a vertex of degree 1 if selected
  • either is part of cycles that would all lead to a vertex of degree 4 if selected

Thus, your 2-3 subgraph is maximal.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I see, however I still don't understand one part: how/when do I know that I should add a "connecting" edge, i.e. an edge that is not a part of any cycle? Say my graph is composed of two circles where one node in one circle and another node in the other circle are connected by an edge. During my DFS I will add both circles to my subgraph, but when should I add the edge connecting the two circles to my subgraph? $\endgroup$ – NayCey Mar 20 at 12:50
  • $\begingroup$ To illustrate what I mean I drew this simple illustration: imgur.com/a/eNDlsxE. We start at node (a) and then proceed with our BFS to node (c) through (b). We then find the cycle on the right hand side and add it to our subgraph. We then go back to node (b). How do we decide if we can add the edge (e) to our subgraph? At that point we don't know if the vertex (b) will be a part of our subgraph (since if the non-filled nodes weren't there, the a-b path couldn't be added). $\endgroup$ – NayCey Mar 20 at 13:18
  • $\begingroup$ Oh you are right, I totally missed these "connecting edges". I have to think about it, but this aswer may not be relevant at all. $\endgroup$ – Vince Mar 20 at 15:28
0
$\begingroup$

I don't have a proof that this works, but I am convinced it is a reasonable start. Perform a DFS with the modification that when a vertex "finishes", if it has degree 1 in the DFS tree (including back edges) delete it. In the case that the root is deleted this way, designate its child as the root and check it again. When this is complete, you should have a maximal subgraph where every vertex has degree at least 2. For each vertex with degree greater than 2, pick an arbitrary back edge incident to that vertex and delete it. Then, go to the other end of that edge and check its degree. If it has dropped to 1, delete it and recurse upward.

Again, I am not positive that this is correct. I wouldn't be surprised if there is some problems, especially in how I said to deal with high degree vertices. I also think there is probably a better modification that can be made to DFS that leads to the "simple" algorithms the author saw. But I hope this is a relatively good start. Good luck!

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Answers given here shall be true, at least you have to be convinced it is true and be prepared to dismiss any refutation attempts. If you do not have proof and do not know whether it is correct, and assume it may fail or simply not handle all cases - this is guess, not an answer. $\endgroup$ – Evil Apr 19 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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