Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Stanislav ZivnýIJCAI 2015

Introduction

Constraint Satisfaction Problems (CSPs) are fundamental to various fields, including scheduling, AI planning, and frequency assignment. Despite their ubiquity, general CSPs are NP-complete. Research into making these problems tractable typically follows two paths: restricting the structure (the graph of variable interactions, such as requiring it to be a tree) or restricting the language (the types of allowed constraints, such as 2-SAT).

This paper proposes a unified framework by examining the microstructure of a CSP—a graph where nodes represent every possible value for every variable. By applying the graph-theoretic concept of topological minors to this microstructure, the authors identify new classes of problems solvable in polynomial time that bridge the gap between structural and language-based restrictions.

Methodology: Path Reduction and Topological Minors

The core innovation lies in adapting the concept of a topological minor to CSP microstructures. In standard graph theory, a graph $H$ is a topological minor of $G$ if $H$ can be formed by deleting edges/nodes or "smoothing out" paths (replacing a path $u-v-w$ with a single edge $u-w$).

The authors define a specific Path Reduction operation for CSPs:

  • When a variable is connected to exactly two others, it can be reduced out, with its constraints projected onto the remaining two variables.
  • This process distinguishes between "positive" edges (allowed assignments) and "negative" edges (forbidden assignments).

To prove tractability, the researchers employ Tutte Decomposition, breaking complex constraint graphs into smaller, 3-connected components. If a forbidden topological minor is absent from the microstructure, these components can be solved independently and their solutions efficiently combined.

Key Insights: A Unified View of Complexity

A significant finding of this work is that properties like acyclicity (the absence of loops in the constraint graph) can be characterized by forbidding a single topological minor. This demonstrates that topological minors are a more expressive tool for describing CSP complexity than simple forbidden sub-patterns.

Furthermore, this approach naturally captures both structural constraints (like bounded treewidth) and language constraints (specific 2-variable constraint types) within a single theoretical framework. The use of path reduction allows for the identification of tractable classes that are significantly broader than those previously identified in the literature.

Key Results and the Complexity Dichotomy

The paper identifies several specific patterns—labeled $Q, M, E_2,$ and $P$—that guarantee polynomial-time solvability when excluded as topological minors from the microstructure.

Figure 3: Specific patterns Q, E2, M, and P that define new tractable classes when excluded as topological minors.

However, not all exclusions lead to tractability. The authors establish a complexity dichotomy, proving that while some patterns ensure efficiency, others remain NP-complete even when forbidden.

Figure 6: Patterns (PS) and (PE) which remain NP-complete even when excluded as topological minors.

Beyond solvability, the paper addresses the recognition problem. Theorem 8.1 demonstrates that for certain patterns, such as the 4-variable pattern $P_{XX}$, determining if a CSP instance belongs to the tractable class (i.e., checking for the presence of the minor) is itself coNP-complete.

Limitations and Future Directions

The primary hurdle for practical application is the hardness of recognition. If identifying an "easy" problem is itself computationally expensive, general-purpose solvers cannot easily pivot to these specialized algorithms.

Future research directions include:

  1. Full Characterization: Determining the complete set of patterns that are topological-minor tractable.
  2. Refining Path Reduction: Developing more sophisticated reduction definitions to capture even larger tractable classes.
  3. Heuristic Integration: Investigating how these topological insights can improve variable elimination heuristics in practical, large-scale CSP solvers.

Summary updated

BibTeX
@inproceedings{cohen2015tractable,
  author = {David A. Cohen and Martin C. Cooper and Peter G. Jeavons and Stanislav Zivný},
  title = {{Tractable Classes of Binary CSPs Defined by Excluded Topological Minors}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure