PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT

Rafael Kiesel, André SchidlerIPEC 2022 · OpenReview

TL;DR

This paper presents DAGer, a solver for the Directed Feedback Vertex Set (DFVS) problem, which aims to find the smallest set of vertices to remove from a directed graph to eliminate all cycles. DAGer leverages a combination of sophisticated graph preprocessing techniques, including adaptations from the vertex cover problem, and a novel approach using an incremental MaxSAT solver to efficiently find solutions.

What Problem Does This Paper Address?

The Directed Feedback Vertex Set (DFVS) problem is a classic NP-complete problem with applications in areas like argumentation frameworks, deadlock detection, and program verification. The goal is to find a minimum set of vertices whose removal breaks all directed cycles in a graph. While the problem is known to be fixed-parameter tractable (meaning it can be solved efficiently if the size of the desired vertex set is small), existing algorithms struggle with instances where the feedback vertex set is large. This paper tackles the challenge of efficiently solving DFVS for larger instances, particularly those encountered in competitive programming challenges like PACE.

Methods

DAGer employs a two-pronged strategy:

  • Preprocessing: The solver first applies a suite of data reduction techniques to simplify the input graph. This includes established DFVS reductions and, importantly, adaptations of techniques originally developed for the Vertex Cover problem. The authors found that many vertex cover reductions can be generalized to DFVS, particularly in cases where cycles are of length two or where vertices are bidirectionally connected.
  • Solving with MaxSAT: Instead of directly encoding the entire problem into a SAT solver (which can lead to an explosion in the number of constraints), DAGer uses a "lazy" approach. It identifies a subset of "short" cycles and encodes them as clauses for a MaxSAT solver. The MaxSAT solver then attempts to find a minimum set of vertices that satisfies these clauses. Crucially, the solver incrementally adds new cycles to the encoding as they are discovered during the solving process, ensuring that only necessary constraints are considered at any given time. This incremental approach, combined with a MaxSAT solver that maximizes satisfied "soft" clauses (representing the negation of vertices being in the DFVS), effectively minimizes the size of the feedback vertex set.

Datasets

Not discussed in the paper. The paper focuses on the solver's performance on instances from the 2022 PACE Challenge.

Key Insights and Ideas

  • Bridging Vertex Cover and DFVS: A significant insight is the successful adaptation of vertex cover data reduction techniques to the DFVS problem. This highlights a common underlying structure between these related graph problems and provides a powerful new set of tools for DFVS preprocessing.
  • Lazy MaxSAT for Scalability: The "lazy" approach to encoding cycles into a MaxSAT solver is key to handling large instances. By incrementally adding cycles only when they are violated by the current partial solution, DAGer avoids the combinatorial explosion of generating all cycles upfront.
  • Incremental Constraint Learning: The MaxSAT solver's ability to learn new clauses when conflicts arise (i.e., when a cycle is found that is not broken by the current candidate DFVS) is crucial for guiding the search effectively.

Key Results

The paper describes DAGer as a solver that achieved good performance on the exact track of the 2022 PACE Challenge. While specific quantitative results (like exact rankings or performance metrics on specific datasets) are not detailed in this short description, the abstract indicates that the approach using MaxSAT with incremental constraints was effective for the instances encountered.

Limitations and Future Work

  • Limited Discussion of Specific Reductions: While the paper mentions adapting vertex cover reductions, a detailed analysis of which specific reductions were adapted and how their soundness for DFVS was proven is left out due to space constraints.
  • MaxSAT Solver Performance: The paper relies on an external MaxSAT solver. The performance is thus dependent on the efficiency of this underlying solver and the effectiveness of the incremental constraint learning.
  • Future Work: The authors suggest that further research could explore more sophisticated adaptations of vertex cover techniques and potentially investigate other constraint satisfaction paradigms beyond MaxSAT.

Summary updated

Abstract

We describe the solver DAGer for the Directed Feedback Vertex Set (DFVS) problem, as it was submitted to the exact track of the 2022 PACE Challenge. Our approach first applies a wide range of preprocessing techniques involving both well-known data reductions for DFVS as well as non-trivial adaptations from the vertex cover problem. For the actual solving, we found that using a MaxSAT solver with incremental constraints achieves a good performance.
BibTeX
@inproceedings{kiesel2022pace,
  author = {Rafael Kiesel and André Schidler},
  title = {{PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT}},
  booktitle = {IPEC},
  year = {2022},
  url = {https://openreview.net/forum?id=Zw2oLaVuwL},
}
Figure