DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.44

The Voice of the Flow: A Graph-Based Approach for Step-Wise Explanations of Constraint Satisfaction Problems

Authors: Minh Anh Nguyen, Tien Mai, and Hoong Chuin Lau

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

Stepwise explanations are an important tool for interpreting constraint programs. Existing methods rely heavily on repeated minimal unsatisfiable subsets (MUS) extraction or intensive SAT-based propagation, which are computationally prohibitive for large-scale problems with complex constraints. We propose a novel framework leveraging Multi-Valued Decision Diagrams (MDDs) to overcome these bottlenecks. By decomposing CSPs into smaller, graph-based subproblems compactly represented as MDDs, we enable highly efficient constraint propagation through network-flow reformulation. To further enhance efficiency, we propose a Divide-and-Conquer approach to improve the search for minimal explanation steps. Furthermore, we utilize the MDD’s network-flow structure to generate nested explanations that break down complex derivation steps into granular, arc-level details, revealing specifically how variable-value assignments become infeasible. In this way, our approach equips the explainer agent with a voice that provides more intuitive and granular stepwise explanations. Evaluated on Graph Coloring and Nurse Rostering benchmarks, our framework significantly reduces explanation generation time while maintaining interpretability and conciseness compared to state-of-the-art methods.

Cite as

Minh Anh Nguyen, Tien Mai, and Hoong Chuin Lau. The Voice of the Flow: A Graph-Based Approach for Step-Wise Explanations of Constraint Satisfaction Problems. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 44:1-44:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nguyen_et_al:LIPIcs.CP.2026.44,
  author =	{Nguyen, Minh Anh and Mai, Tien and Lau, Hoong Chuin},
  title =	{{The Voice of the Flow: A Graph-Based Approach for Step-Wise Explanations of Constraint Satisfaction Problems}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{44:1--44:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.44},
  URN =		{urn:nbn:de:0030-drops-266763},
  doi =		{10.4230/LIPIcs.CP.2026.44},
  annote =	{Keywords: overconstraint, explanation, propagation, multi-valued decision diagrams}
}

Search Results

Documents authored by Mai, Tien

The Voice of the Flow: A Graph-Based Approach for Step-Wise Explanations of Constraint Satisfaction Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message