The Pebble Game Algorithm

This post will be about Problem C in the DABOI Round 1.

There is no English statement, so here is a summary.

You are given a graph, and you must determine if the graph is rigid. A graph is considered rigid if, when the edge lengths and the positions of two vertices in 2D space are fixed, no other valid configurations of the graph exist. For example, a square can deform into a rhombus, but a triangle is rigid and cannot be reshaped without changing its edge lengths.

The model solution involved setting an arbitrary edge as fixed and adding nodes if it forms a cycle of 3. However, this turns out not to work because there exists rigid graphs which do not have a cycle of 3 in them.

The Pebble Game Algorithm#

There exists a more robust method from rigidity theory known as the Pebble Game Algorithm. The Pebble Game Algorithm allows us to check the rigidity of a graph by tracking the degrees of freedom and dependencies in the graph. Initially, each vertex has 2 degrees of freedom, corresponding to its position in 2-dimensional space.

The algorithm assigns each vertex “pebbles” to represent these degrees of freedom. Adding an edge between two vertices removes one pebble (i.e., restricts one of their relative movements)

Details#

1. Start with a set of n vertices where each vertex has 2 pebbles on it

2. For each edge (u, v) that you would like to add:

   • Check if the number of pebbles at vertices u and v are both 2
     • If so, add a directed edge from u to v and remove a pebble from u
     • Otherwise:
       • Perform a path search (like DFS) in the directed graph to locate an extra pebble
       • If a path is found, reverse the edges on this path and give the extra pebble to u or v
       • Repeat until both u and v have 2 pebbles
   • If this process is impossible, then this edge is redudant and should not be added

3. To check if a graph is rigid, check if the number of edges that were successfully added equals 2n - 3

   • This correspounds with the fact that a rigid graph should have 3 degrees of freedom (rotation and position in 2-dimensional space)

Implementation#

Here is an implementation of the Pebble Game Algorithm in C++:

#include <vector>
#include <numeric>
#include <algorithm>

class pebble_game {
  private:
    int num_vertices, num_edges;
    std::vector<int> pebbles;
    std::vector<std::vector<bool>> dir;
    std::vector<std::vector<int>> adj;
    std::vector<bool> visited;

    bool dfs(int u) {
        visited[u] = 1;
        if(pebbles[u] > 0) {
            pebbles[u]--;
            return 1;
        }
        for(int v: adj[u]) {
            if(!visited[v] && dir[u][v]) {
                if(dfs(v)) {
                    dir[u][v] = 0;
                    dir[v][u] = 1;
                    return 1;
                }
            }
        }
        return 0;
    }

    bool move_pebbles(int u, int v) {
        std::fill(visited.begin(), visited.end(), 0);
        visited[u] = visited[v] = 1;
        for(int o: adj[u]) {
            if(!visited[o] && dir[u][o]) {
                if(dfs(o)) {
                    dir[u][o] = 0;
                    dir[o][u] = 1;
                    pebbles[u]++;
                    return 1;
                }
            }
        }
        return 0;
    }

  public:
    pebble_game(int n) : num_vertices(n), num_edges(0), pebbles(n, 2), dir(n, std::vector<bool>(n)), visited(n), adj(n) {}

    bool is_rigid() const {
        return num_edges == (2 * num_vertices - 3);
    }

    bool add_edge(int u, int v) {
        if(is_rigid()) return 0;
        int cnt = 0;
        while(pebbles[u] < 2) {
            if(!move_pebbles(u, v)) break;
        }
        while(pebbles[v] < 2) {
            if(!move_pebbles(v, u)) break;
        }
        if(pebbles[u] + pebbles[v] == 4) {
            adj[u].push_back(v);
            adj[v].push_back(u);
            dir[u][v] = 1;
            dir[v][u] = 0;
            pebbles[u]--;
            num_edges++;
            return 1;
        } else return 0;
    }
};