Source-linked AI summary
Pebble Game Algorithms and Sparse Graphs
Audrey Lee, Ileana Streinu
TL;DR
The paper develops pebble game algorithms to recognize sparse graphs across the full range ℓ∈[0, 2k), while solving fundamental decision, spanning, extraction, and optimization problems. These algorithms run in O(n2) time and characterize sparse, tight, spanning, and other graph classes.
Problem
The paper studies decision, spanning, extraction, and optimization problems for sparse and tight graphs.
Method
The paper introduces (k,ℓ)-pebble games and proves their graph-recognition characterization across the full range ℓ∈[0, 2k).
Results
O(n2) time; pebble games recognize exactly the (k,ℓ)-sparse graphs and classify under-constrained, well-constrained, and over-constrained graphs as sparse, tight, and spanning, respectively.
Takeaways & Limitations
The basic pebble game solves decision, extraction, spanning, and weighted optimization problems for sparse graphs.
Takeaways & Limitations
Component pebble games require O(n2) space in the upper range because of an additional matrix; an O(n)-space alternative does not solve optimization.
Abstract
from arXiv · showhide
A multi-graph $G$ on $n$ vertices is $(k,\ell)$-sparse if every subset of $n'\leq n$ vertices spans at most $kn'- \ell$ edges. $G$ is {\em tight} if, in addition, it has exactly $kn - \ell$ edges. For integer values $k$ and $\ell \in [0, 2k)$, we characterize the $(k,\ell)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,\ell)$-pebble games.
1 Introduction
The paper introduces pebble games that exactly characterize (k,ℓ)-sparse graphs across the full range ℓ∈[0,2k), extending prior specialized algorithms to fundamental recognition, extraction, spanning, optimization, and component problems.
- Definitions: (k,ℓ)-sparse graphs require every n′-vertex subset to span at most kn′−ℓ edges, while tight graphs attain kn−ℓ total edges.The paper also allows loops and multiple edges in its multigraph model.
- Background: Prior work connected sparse graphs to matroids, spanning-tree decompositions, rigidity, arborescences, and Henneberg constructions.These connections motivate the algorithmic study of sparse graph classes.
- Prior algorithms: Existing pebble-game and related algorithms addressed special cases, but the authors found no algorithms applicable to all (k,ℓ)-sparse graphs or (k,a)-arborescences.For ℓ∈[0,k], Gabow and Westermann provided O(n^3/2) algorithms, whereas the full range lacked better alternatives than pebble games.
- Contribution: The paper defines (k,ℓ)-pebble games and proves that they recognize exactly the (k,ℓ)-sparse graphs for every ℓ∈[0,2k).The work presents this as the full generalization of Jacobs and Hendrickson’s (2,3)-pebble game.
- Applications: The algorithms address decision, spanning, extraction, weighted optimization, and component computation for sparse graphs.The component problem identifies maximal tight induced subgraphs, and weighted optimization extracts a maximum-weight sparse subgraph.
- Complexity: The pebble game algorithms run in O(n^2) time using simple data structures, matching the complexity of a matching-based algorithm for two-dimensional rigidity.For the special range ℓ∈[0,k], O(n^3/2) algorithms are known, but no better algorithms are known across the entire sparse-graph range.
2 Properties of Sparse Graphs
The section establishes structural and matroidal properties of (k,ℓ)-sparse graphs, including parameter-range restrictions, tight-graph bases, and component behavior.
- Parameter ranges: The natural parameter range is ℓ∈[0, 2k), with lower, upper, and special Szegő subranges requiring different structural treatment.The upper range is ℓ∈[k,2k), and the Szegő range is a further upper-range subdivision.
- Parameter ranges: When ℓ≥2k, sparse graphs contain only the empty graph; when ℓ<0, even disjoint sparse graphs need not have a sparse union.These boundary cases motivate restricting attention to ℓ∈[0,2k).
- Basic properties: Sparse graphs permit at most k−ℓ loops per vertex and at most 2k−ℓ parallel edges, becoming loopless when ℓ≥k.In the upper range, single-vertex tight graphs do not exist, and Szegő-range tight graphs have additional minimum-size restrictions.
- Matroidal structure: For admissible parameter ranges, (k,ℓ)-tight graphs on n vertices form the bases of a sparsity matroid over a complete multigraph with loop multiplicity k−ℓ and edge multiplicity 2k−ℓ.The basis-exchange proof uses blocks containing the endpoints of a candidate edge and removes an edge from the resulting maximal block.
- Algorithmic implications: The matroid property justifies arbitrary edge-insertion order in pebble-game algorithms and greedy optimization over sparse subgraphs.Independent edges can be added until tight, with blocks serving as the obstructions to further additions.
3 The basic (k, ℓ)-Pebble Game Algorithm
The basic (k,ℓ)-pebble game processes graph edges in arbitrary order using pebble movements and orientations, then classifies the input by which edges it can accept.
- Correctness: The paper proves that the pebble game is a decision algorithm for sparse graphs, with correctness established after the algorithmic description.The basic version is later extended to a more efficient component-aware version.
- Game setup: The game starts with k pebbles on each vertex, and an accepted edge requires at least ℓ+1 pebbles across its two endpoints.Edges are inserted and oriented, while pebbles may be moved and existing edges reoriented according to the game rules.
- Algorithm: The algorithm considers every input edge in arbitrary order and either accepts or rejects it while performing the permitted pebble-game moves.Its final classification distinguishes Well-constrained, Under-constrained, Over-constrained, and Other inputs.
- Complexity: For constant k and ℓ, the basic game takes O(n^3) time and O(n) space on dense O(n^2)-edge inputs.The accepted-edge count is O(kn), the auxiliary digraph uses O(kn) space, and each input edge is considered once.
4 Pebble Game Graphs coincide with Sparse Graphs
The pebble game maintains directed-graph invariants while processing edges, and its classifications coincide exactly with sparse, tight, spanning, and neither classes. The basic game also solves decision, extraction, spanning, and weighted optimization problems.
- Classification: Under-constrained, Well-constrained, and Over-constrained game graphs are sparse, tight, and spanning, respectively; Other graphs are neither sparse nor spanning.The equivalence is stated as a theorem and refined by the classification lemma.
- Applications: The basic pebble game solves decision, extraction, spanning, and weighted optimization problems for sparse graphs.Optimization requires inserting edges in sorted order of their weights.
- Algorithm: The basic pebble game initializes k pebbles on every vertex and processes a graph using a maintained directed graph D.The input may contain loops and multiple edges; the algorithm outputs one of four classifications.
- Invariants: The game maintains vertex and vertex-set invariants linking free pebbles, spanned edges, and outgoing edges to k and kn′, respectively.For vertex sets, peb(V′) + span(V′) + out(V′) = kn′, while peb(v) + span(v) + out(v) = k.
- Invariants: A vertex subset spans a block exactly when its free-pebble and outgoing-edge counts sum to ℓ.This follows directly from the fourth invariant and identifies the structural condition used by the game.
- Classification: An edge is inserted if and only if it is independent in the current directed game graph.Repeated pebble searches can gather ℓ+1 pebbles on the endpoints of an independent edge, enabling insertion.
5 Component Pebble Games
Component pebble games augment the basic pebble game with component maintenance and detection, preserving recognition while improving efficiency to O(n^2). They correctly compute components and support several fundamental graph problems.
- Component Detection: Two component-detection algorithms identify newly formed components after edge insertion: one searches incoming edges from a detected block, while the other finds its complement.The first approach generalizes Jacobs and Hendrickson’s method; the second requires no special treatment for ℓ = 0.
- Component Maintenance: For ℓ = 0, components use marking; for ℓ ∈ (0, k], they use vertex labels; for ℓ ∈ (k, 2k), overlapping components use vertex sets and an n × n query matrix.The matrix answers in constant time whether two vertices share a component.
- Correctness: Theorem 16 states that component pebble games recognize the same graphs as basic pebble games and compute components correctly.Correctness follows because detected maximal subgraphs with exactly ℓ pebbles are blocks, and components are characterized from those blocks.
- Component Pebble Games: Component pebble games maintain components in the directed pebble-game graph and reject edges whose endpoints lie in an existing component.The component version otherwise uses the same input, output, and directed graph as the basic game.
- Complexity: O(n^2) time is achieved because dependent edges are rejected in constant time and component detection with data-structure updates is linear.The improved component algorithm is one order of magnitude faster than the basic algorithm described immediately beforehand.
- Complexity: Space is linear in the lower range but O(n^2) in the upper range because component maintenance uses an additional matrix.An O(n)-space alternative requires a specific edge order and does not solve Optimization.
6 Applications
The applications section uses pebble games to construct Henneberg sequences and address circuits and redundancy. It establishes quadratic-time Henneberg reduction and linear-time circuit detection within the stated graph classes.
- Henneberg Sequences: Henneberg sequences provide inductive constructions for Laman graphs and other rigid structures, and the paper extends this construction framework to tight sparse graphs.Each inductive step removes selected edges before adding a vertex of degree k + b, with b ∈ [0, k].
- Henneberg Sequences: A tight graph admits a Henneberg reduction step: after removing an edge incident to a degree k + b vertex, another edge can restore tightness.For ℓ ∈ [0, 3k/2], the replacement edge is found among the vertex’s neighbors; otherwise, a larger base-case-satisfying set is used.
- Henneberg Sequences: Bounded-degree vertices enable repeated reduction steps, and iterating them reaches a base case to compute the full Henneberg sequence.The reduction uses the fact that a sparse graph has a vertex of degree in [k, 2k].
- Henneberg Sequences: O(n^2) time solves the Henneberg reduction problem using the pebble game.Each edge removal restores a pebble, and the necessary insertion searches examine only a constant-size vertex subset.
- Circuits and Redundancy: Circuits associated with dependent edges are found by collecting ℓ pebbles on the edge endpoints and computing Reach(u, v).The circuit consists of the edges spanned by Reach(u, v) together with the dependent edge.
- Circuits and Redundancy: Redundancy is decided by marking edges in detected circuits; if every edge is marked, the graph is redundant, and these algorithms run in O(mn) time.If edges remain unmarked, they are bridges, and the resulting sparsity components correspond to redundant components.