6
$\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$
  • $\begingroup$ Let $U \subseteq V$ of the vertices of graph $G$ such that degree of every vertex in $U$ is at most three. Now consider the new graph $G = G[U]$ (induced subgraph). Case 1 : Let us assume that $G[U]$ have maximum degree $2$. The such kind of graphs are either paths or cycles in which finding $2$ subgraph is easy. $\endgroup$ – Shiv Jan 14 at 11:04
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 '19 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 '19 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$ – Optidad Mar 20 '19 at 15:28

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.