PACE Solver Description: Hydra Prime

Yosuke Mizutani, David Dursteler, Blair D. SullivanIPEC 2023 · OpenReview

TL;DR

This paper presents Hydra Prime, a winning solver for the 2023 PACE Challenge on computing twin-width. It introduces two novel techniques, "timeline encoding" and "hydra decomposition," which significantly improve the efficiency of finding this complex graph parameter. These methods allow for faster local search and iterative refinement, making exact twin-width computation more practical.

What Problem Does This Paper Address?

The paper tackles the challenge of computing "twin-width," a structural graph parameter that quantifies how close a graph is to a cograph. Cographs are graphs that can be reduced to a single vertex by repeatedly merging pairs of "twins" (vertices with identical neighbors). Twin-width generalizes this by measuring the minimum "mistakes" (red edges) made during this merging process when vertices are not perfect twins. While twin-width is crucial for many efficient graph algorithms (FPT algorithms), computing it exactly is NP-hard and has historically been computationally expensive, even for moderately sized graphs. The PACE Challenge aims to push the boundaries of exact computation for such parameters.

Methods

Hydra Prime employs a multi-pronged approach. It begins by leveraging modular decomposition to break down the input graph into a hierarchy of "prime graphs." The twin-width of the original graph is then the maximum twin-width of these prime graphs. This decomposition is a standard starting point, but Hydra Prime enhances it.

The core innovations are:

  • Timeline Encoding: This is a novel data structure designed to efficiently compute the "width" of a given contraction sequence. It stores "red sources" and "intervals" that track the cause and duration of red edges. This allows for faster local search by enabling quick updates and queries about red edge overlaps.
  • Hydra Decomposition: This is an iterative refinement strategy that uses small vertex separators. It's an advanced technique for finding upper and lower bounds on twin-width. The process involves recursively partitioning the graph, contracting parts, and joining them back, aiming to refine the contraction sequence and improve the bound.

The solver alternates between various upper- and lower-bound algorithms, including exact solvers for tree-like structures and SAT-based solvers for more complex cases, all applied to the prime graphs.

Datasets

Not discussed in the paper. The paper focuses on the algorithms and their performance on the benchmark instances provided by the PACE Challenge.

Key Insights and Ideas

  • Modular decomposition is a powerful preprocessing step: Decomposing a graph into prime graphs significantly simplifies the problem, as the twin-width of the whole graph is determined by the maximum twin-width of its components.
  • Timeline encoding revolutionizes contraction sequence analysis: By efficiently tracking red edges and their impact over time, this data structure dramatically speeds up the evaluation of contraction sequences, crucial for local search.
  • Hydra decomposition offers a structured refinement: This iterative strategy, using vertex separators, provides a systematic way to improve bounds on twin-width by breaking down complex graphs into manageable subproblems.
  • Combining diverse algorithms is key: The success of Hydra Prime lies in its ability to strategically apply a suite of algorithms (exact solvers, lower-bound, upper-bound, SAT-based) to different parts of the decomposed graph.

Key Results

Hydra Prime achieved winning performance in the Exact Track of the 2023 PACE Challenge. While specific quantitative results (e.g., exact twin-width values for specific graphs or speedup percentages) are not detailed in this description paper, the victory itself signifies a significant advancement in the practical computation of twin-width. The paper highlights that the novel timeline encoding and hydra decomposition were key contributors to this success.

Limitations and Future Work

  • Computational Complexity: While Hydra Prime significantly improves practical performance, computing twin-width remains NP-hard. The paper doesn't detail the exact complexity bounds for their novel techniques, but they are designed to make the problem tractable for larger instances than previously possible.
  • SAT Solver Dependency: Some of the algorithms rely on SAT solvers, whose performance can be unpredictable. The paper mentions using the Kissat solver.
  • Future Work: The paper suggests that the novel techniques introduced (timeline encoding and hydra decomposition) are foundational and can likely be further optimized or applied to related graph parameters. The appendix mentions additional details available on the code repository, hinting at further algorithmic refinements.

Summary updated

Abstract

This note describes our submission to the 2023 PACE Challenge on the computation of twin-width. Our solver Hydra Prime combines modular decomposition with a collection of upper- and lower-bound algorithms, which are alternatingly applied on the prime graphs resulting from the modular decomposition. We introduce two novel approaches which contributed to the solver’s winning performance in the Exact Track: timeline encoding and hydra decomposition. Timeline encoding is a new data structure for computing the width of a given contraction sequence, enabling faster local search; the hydra decomposition is an iterative refinement strategy featuring a small vertex separator.
BibTeX
@inproceedings{mizutani2023pace,
  author = {Yosuke Mizutani and David Dursteler and Blair D. Sullivan},
  title = {{PACE Solver Description: Hydra Prime}},
  booktitle = {IPEC},
  year = {2023},
  url = {https://openreview.net/forum?id=asVn953U0b},
}
Figure