Find all chordless cycles in an undirected graph

Question

How to find all chordless cycles in an undirected graph?

For example, given the graph

0 --- 1
|     | \
|     |  \
4 --- 3 - 2

the algorithm should return 1-2-3 and 0-1-3-4, but never 0-1-2-3-4.

---

(Note that This question is not the same as small cycle finding in a planar graph because the graph is not necessarily planar)

I have read the paper Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion but I don't understand what they're doing. I have also tried CYPATH but the program only gives the count, algorithm EnumChordlessPath in readme.txt has significant typos, and the C code is a mess.

I am not trying to find an arbitrary set of fundametal cycles. Cycle basis can have chords.

Ikeikebana

@aioobe: No constraint, but that would be too inefficient. – Ikeikebana

I doesn't do much good to post a link to a paper behind a paywall. – Mexican

@Beta: sometimes it does -- references to papers are useful, + ACM is not exactly an obscure technical journal. (though I don't have access to it either) – Cession

@Kenny: Is there more than one way of constructing cycle bases? Something seems fishy here... looks like chordless cycles form a basis, but I could be missing something obvious. – Cession

@jason: yes. Consider the complete 4-graph, which has 4 different ways to choose a basis (of 3 triangles). There can be more chordless cycles than the number of basis. – Ikeikebana

Why is a math.sx moderator asking this question here? Are you after implementations? Asking "Are there any interesting properties of the class of chordless graphs that would help me generate them efficiently?" sounds like a more useful starting point to me, given that it seems that your motivation is to get a feel for the search space, not just throw together a hack. – Minne

@Charles: Of course I'm after implementation, or an algorithm that is written in pseudo-code that can be implemented easily. – Ikeikebana

@Kenny: I had not paid attention to the [language-agnostic] tag, sorry. But if you do care about implementation, don't you have some sort of worst-case performance constraint in mind? aioobe's solution is only in EXPTIME, which is perfectly feasible when n is bounded by a small constant... – Minne

How is this different from finding the minimum cycle basis of a graph? (#16783398) – Apterygial

This might be useful: arxiv.org/pdf/1309.1051.pdf – Darien

Answer 1

Assign numbers to nodes from 1 to n.

1. Pick the node number 1. Call it 'A'.

2. Enumerate pairs of links coming out of 'A'.

3. Pick one. Let's call the adjacent nodes 'B' and 'C' with B less than C.

4. If B and C are connected, then output the cycle ABC, return to step 3 and pick a different pair.

5. If B and C are not connected:

   • Enumerate all nodes connected to B. Suppose it's connected to D, E, and F. Create a list of vectors CABD, CABE, CABF. For each of these:
   • if the last node is connected to any internal node except C and B, discard the vector
   • if the last node is connected to C, output and discard
   • if it's not connected to either, create a new list of vectors, appending all nodes to which the last node is connected.

   Repeat until you run out of vectors.

6. Repeat steps 3-5 with all pairs.

7. Remove node 1 and all links that lead to it. Pick the next node and go back to step 2.

Edit: and you can do away with one nested loop.

This seems to work at the first sight, there may be bugs, but you should get the idea:

void chordless_cycles(int* adjacency, int dim)
{
    for(int i=0; i<dim-2; i++)
    {
        for(int j=i+1; j<dim-1; j++)
        {
            if(!adjacency[i+j*dim])
                continue;
            list<vector<int> > candidates;
            for(int k=j+1; k<dim; k++)
            {
                if(!adjacency[i+k*dim])
                    continue;
                if(adjacency[j+k*dim])
                {
                    cout << i+1 << " " << j+1 << " " << k+1 << endl;
                    continue;
                }
                vector<int> v;
                v.resize(3);
                v[0]=j;
                v[1]=i;
                v[2]=k;
                candidates.push_back(v);
            }
            while(!candidates.empty())
            {
                vector<int> v = candidates.front();
                candidates.pop_front();
                int k = v.back();
                for(int m=i+1; m<dim; m++)
                {
                    if(find(v.begin(), v.end(), m) != v.end())
                        continue;
                    if(!adjacency[m+k*dim])
                        continue;
                    bool chord = false;
                    int n;
                    for(n=1; n<v.size()-1; n++)
                        if(adjacency[m+v[n]*dim])
                            chord = true;
                    if(chord)
                        continue;
                    if(adjacency[m+j*dim])
                    {
                        for(n=0; n<v.size(); n++)
                            cout<<v[n]+1<<" ";
                        cout<<m+1<<endl;
                        continue;
                    }
                    vector<int> w = v;
                    w.push_back(m);
                    candidates.push_back(w);
                }
            }
        }
    }
}

Londrina

Reviving an oldie :) What did you mean with internal node in "if the last node is connected to any internal node except C and B, discard the vector"? Unfortunately I can't really read your code. Is it the pure definition of an internal node, i.e. one with a child, or do you mean 'a node in the vector'? The last one I follow, but if it's just 'an internal node' - how can it not be connected if the shape isn't a triangle? – Valedictory

Answer 2

@aioobe has a point. Just find all the cycles and then exclude the non-chordless ones. This may be too inefficient, but the search space can be pruned along the way to reduce the inefficiencies. Here is a general algorithm:

void printChordlessCycles( ChordlessCycle path) {

  System.out.println( path.toString() );
  for( Node n : path.lastNode().neighbors() ) {

    if( path.canAdd( n) ) {

      path.add( n);
      printChordlessCycles( path);
      path.remove( n);
    }
  }
}

Graph g = loadGraph(...);
ChordlessCycle p = new ChordlessCycle();
for( Node n : g.getNodes()) {
  p.add(n);
  printChordlessCycles( p);
  p.remove( n);
}

class ChordlessCycle {
   private CountedSet<Node> connected_nodes;
   private List<Node> path;

   ...

   public void add( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.increment( neighbor);
     }
     path.add( n);
   }

   public void remove( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.decrement( neighbor);
     }
     path.remove( n);
   }

   public boolean canAdd( Node n) {
     return (connected_nodes.getCount( n) == 0);
   }
}

Lenardlenci

Answer 3

Just a thought:

Let's say you are enumerating cycles on your example graph and you are starting from node 0.

If you do a breadth-first search for each given edge, e.g. 0 - 1, you reach a fork at 1. Then the cycles that reach 0 again first are chordless, and the rest are not and can be eliminated... at least I think this is the case.

Could you use an approach like this? Or is there a counterexample?

Cession

Answer 4

How about this. First, reduce the problem to finding all chordless cycles that pass through a given vertex A. Once you've found all of those, you can remove A from the graph, and repeat with another point until there's nothing left.

And how to find all the chordless cycles that pass through vertex A? Reduce this to finding all chordless paths from B to A, given a list of permitted vertices, and search either breadth-first or depth-first. Note that when iterating over the vertices reachable (in one step) from B, when you choose one of them you must remove all of the others from the list of permitted vertices (take special care when B=A, so as not to eliminate three-edge paths).

Mexican

Answer 5

Find all cycles.

Definition of a chordless cycle is a set of points in which a subset cycle of those points don't exist. So, once you have all cycles problem is simply to eliminate cycles which do have a subset cycle.

For efficiency, for each cycle you find, loop through all existing cycles and verify that it is not a subset of another cycle or vice versa, and if so, eliminate the larger cycle.

Beyond that, only difficulty is figuring out how to write an algorithm that determines if a set is a subset of another.

Anatole

it's a good idea but my gut feeling is that it probably suffers from combinatorial explosions for large graphs. See the # of cycles in a complete graph: mathworld.wolfram.com/CompleteGraph.html. For the complete graph K16, the # of cycles is 1904975488436 but the # of chordless cycles is the # of 3-vertex cycles = (16*15*14)/(3*2*1) = 560. – Cession

That's unavoidable. I don't have the proof handy, but I can almost guarantee that you'd have to iterate through them all before you can find all chordless cycles. However rather than having each cycle check against all other cycles after you've found all combinations, you can eliminate them as you get them, meaning you reduce the memory and workload for your second pass. In other words, time for graph K16 would be O(1904975488436 * 560) rather than O(1904975488436^2). – Anatole

"but I can almost guarantee that you'd have to iterate through them all before you can find all chordless cycles." I disagree; if you are doing a breadth-first traverse of the graph, and you find a chordless cycle, that immediately eliminates a big chunk of the search space. – Cession

You realize that's a bit like saying that if you find a semi-decent solution to the traveling salesman problem that you're probably not far from the best solution thus you eliminate a big chunk of the search space by looking at similar solutions. It's an unfortunate reality that you must check all possibilities which is the power set of all points in the graph. – Anatole