# Hypergraph Neural Networks Accelerate MUS Enumeration

Source: [Hypergraph Neural Networks Accelerate MUS Enumeration](<https://www.sota2.com/research/paper/69dc78607d0172140ec78908>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-14T05:00:04.234Z

Authors: Hiroya Ijima, Koichiro Yawata

Published: 2026-04-10T06:13:41.000Z

## Abstract

Enumerating Minimal Unsatisfiable Subsets (MUSes) is a fundamental task in constraint satisfaction problems (CSPs). Its major challenge is the exponential growth of the search space, which becomes particularly severe when satisfiability checks are expensive. Recent machine learning approaches reduce this cost for Boolean satisfiability problems but rely on explicit variable-constraint relationships, limiting their application domains. This paper proposes a domain-agnostic method to accelerate MUS enumeration using Hypergraph Neural Networks (HGNNs). The proposed method incrementally builds a hypergraph with constraints as vertices and MUSes enumerated until the current step as hyperedges, and employs an HGNN-based agent trained via reinforcement learning to minimize the number of satisfiability checks required to obtain an MUS. Experimental results demonstrate the effectiveness of our approach in accelerating MUS enumeration, showing that our method can enumerate more MUSes within the same satisfiability check budget compared to conventional methods.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [MUS/MSS Enumeration on SAT small](<https://www.sota2.com/research/sota/mus-mss-enumeration-on-sat-small.md>): MUS/MSS Enumeration; SAT small; Normalized Count: 3.29.

- [MUS/MSS Enumeration on SAT large](<https://www.sota2.com/research/sota/mus-mss-enumeration-on-sat-large.md>): MUS/MSS Enumeration; SAT large; Number of MUSes/MSSes: 130.6.

- [MUS/MSS Enumeration on GC](<https://www.sota2.com/research/sota/mus-mss-enumeration-on-gc.md>): MUS/MSS Enumeration; GC; Count of MUS/MSS: 31.6.

- [MUS/MSS Enumeration on SMT](<https://www.sota2.com/research/sota/mus-mss-enumeration-on-smt.md>): MUS/MSS Enumeration; SMT; Count of MUSes/MSSes: 58.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2604.09001>)

[PDF](<https://arxiv.org/pdf/2604.09001.pdf>)