Overview

HTTPS SSH

About

This is the code that we submitted to Track B of the first PACE challenge. The challenge was to write code that finds a smallest feedback vertex set (fvs) of an input graph. We came up fifth among seven teams in the competition.

The team

Shivam Garg, G. Philip, and Apoorva Tamaskar

Running the code

Pre-requisites

  • Python3. Tested against version 3.5.2.
  • python-igraph. Tested against version 0.7.1-5.

To install these on (e.g.) Debian, do:

  • Install python3.

    • Debian's version is currently (always?) a bit old, but that should hopefully not be much of a problem for something as stable as Python.
  • Install python3-setuptools.

  • Run easy_install python-igraph

Installation

This one's easy: Just download fvs.py and put it wherever you like.

Running

python3 -O fvs.py <path to input-file>

Here input-file is a file that contains the description of a graph in the format prescribed by the PACE competition.

Output

The program outputs a list of vertex names, one per line, of a smallest feedback vertex set of the input graph.

The algorithm.

Overview

At a high level, our code is an implementation of the following simple algorithm, using the igraph library for graph operations:

  • Apply degree-0, 1, 2 reduction rules to get an equivalent graph of minimum degree at least 3.
  • Find a smallest cycle in the graph.
  • Branch on the vertices of this graph.

Details

The code implements some simple optimizations so that it doesn't (hopefully) take forever to run on moderately large instances. Here is a more detailed descripton of the code:

  1. Read the input file and construct a graph object. Note that all graph operations use the igraph library.
  2. Apply the degree-0, 1, 2 reduction rules to get:

    • A reduced graph, possibly with multiple edges, whose minimum degree is at least 3. This graph does not contain loops, because every loop vertex is deleted from the graph and included in:

    • A partial feedback vertex set of the original graph, consisting of all those vertices which attain loop edges during the reduction process.

  3. Compute two lower bounds on the size of an fvs of the reduced graph:

    • One bound is based on a degree argument, taking advantage of the fact that the reduced graph has minimum degree at least 3.

    • The other bound is based on greedily packing smallest cycles in the reduced graph, and counting the size of such a packing.

  4. Add the size of the partial fvs from step 2 to the higher of these two bounds, to obtain the "current lower bound" (CLB).

  5. Branch on the vertices of a shortest cycle in the reduced graph, to find a smallest fvs of the reduced graph. We describe this branching in more detail below.

  6. Output the list of vertices of the partial fvs from step 2 and those of the fvs obtained in step 5.

The branching algorithm

This algorithm branches on the vertex set of a shortest cycle of the reduced graph G. It employs some heuristics to try to bound the maximum branching depth. Following is a description of the main features of this algorithm:

  1. The algorithm keeps track of the best fvs of G that we have found so far, at all times. In the beginning we apply a greedy approximation algorithm (pick the vertex with the largest degree, apply the reduction rules, and repeat) to get an approximation to the smallest fvs. This is our best fvs at this point.

  2. We compute a CLB for the size of an fvs of G, exactly as in step 3 of the above algorithm. If the lower and upper bounds match, we have found a smallest fvs, and we return this fvs. Otherwise, we branch.

  3. Our branching algorithm is as follows: We first find a smallest cycle in the graph. Let this cycle be v1, v2, ... , vp, v1.

    • We find a smallest fvs F1 that contains the vertex v1. If the size of F1 matches the CLB for the graph, then we return this fvs. Otherwise we store F1 as our "best fvs" (BFVS) so far, and

    • we find a smallest fvs F2 that does not contain v1, and contains v2. If the size of F2:

      • matches the CLB, then we return F2

      • is smaller than the size of F1, then we update our BFVS to F2

    • If we did not return F2 in the previous step, then we find an fvs F3 that does not contain either of v1, v2, and contains v3. We then process F3 exactly as we did for F2.

    • We keep doing this for successive vertices on the cycle, till we either:

      • Find an fvs F whose size matches our current lower bound, in which case we return F, or;

      • Run out of vertices to branch on, in which case we return the then BFVS as a smallest fvs of the graph.

  4. We use the following heuristics to speed up the branching:

    1. We do the branching "depth-first" rather than "breadth-first". That is, let G1 = G be the reduced graph with which we start, and let C1 be the first cycle of G1 that we branch on. We do not branch on all the vertices of C1 one after the other, as in the above description. Instead, we do the following:

    2. Let v1 be the first vertex of C1. We pick v1 into our solution, delete v1 from graph G1, and apply the reduction rules to the remaining graph to obtain graph G2.

    3. We then find a shortest cycle C2 of G2, pick the first vertex v2 of C2 into our solution, and apply the reduction rules to the remaining graph to obtain graph G3.

    4. We keep doing this till the remaining graph is empty.

    Note that we go "deeper" into the branching tree first; that is, our branching picks vertices from disjoint cycles in preference to vertices from the same cycle. The intuitive reason to do this is that deleting vertices in this fashion is likely to result in a structurally simple (e.g: a disjoint collection of unicyclic graphs) graph sooner rather than later. This hunch has no theoretical basis (so far), but it seems to work well in practice.

    We implement this "depth-first" branching by storing partially processed graphs (those we obtain by deleting a vertex from a shortest cycle) in a queue, and processing these partial solutions in queue order.

    1. Whenever it becomes clear that any fvs that we will find would not be smaller than the current best fvs that we have found, we stop our processing and abort the rest of that branch.

    2. Before branching on a new cycle, we check if our current partial solution is comparable in size to the current best fvs that we have. If this is indeed the case, then we find a lower bound for the fvs size of the remaining graph, and check if size(current partial solution) + lower_bound(remaining graph) is no smaller than the size of our current best fvs. If this is the case, then we abort this branch.

    At present the notion of "comparable" is: partial-fvs-size &gt;= current-best-fvs-size/3 . This fraction was chosen empirically.