Research map / Learning theory and algorithms / Combinatorial and search optimization
On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that disjunctive ASP admits a polynomial kernel in vertex cover size (single-exponential algorithm), while reductions from normal to disjunctive programs yield ETH-tight double-exponential lower bounds for treedepth, feedback vertex size, cliquewidth, pathwidth, bandwidth and cutwidth.
Problem
Structural parameterized complexity of disjunctive Answer Set Programming (consistency checking) with respect to rule-structure (incidence/primal graph) parameters between vertex cover size and treewidth, where treewidth yields double-exponential runtime.
Approach
A polynomial kernel for disjunctive ASP in vertex cover size of the incidence/primal graph, plus a novel reduction from normal (normalized fully tight) to disjunctive programs that uses disjunction and bit-pointers to exponentially compress feedback vertex size, treedepth, and treewidth, yielding ETH-tight double-exponential lower bounds.
Key results
- Polynomial kernel for disjunctive ASP in vertex cover size: |at(Π')| ≤ 4^c·C(|S|,c), giving 2^{2·4^c·C(k,c)} poly runtime.
- Reduction compresses feedback vertex size from k to O(log k), yielding ETH-tight 2^{2^{o(k)}} lower bounds for FVS, treedepth, pathwidth, cliquewidth, bandwidth, cutwidth.
- Treewidth compression lemma gives TW O(log k) for normalized fully tight programs, implying double-exponential lower bounds in treewidth.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a polynomial kernel parameterized by primal-graph vertex cover size | Disjunctive ASP consistency · Bounded-rule-size programs, primal-graph vertex cover size k | runtime: O(22·4c( k c ) poly(|at(Π)|)) | Helped |
| Reduce from normal ASP to disjunctive ASP, compressing feedback vertex size exponentially | Disjunctive ASP consistency · Incidence-graph feedback vertex size | runtime lower bound: 22o(k) · poly(|at(Π)|) | Hurt |
| Apply the structural-compression reduction | Disjunctive ASP consistency · Incidence-graph distance to almost paths | runtime lower bound: 22o(k) · poly(|at(Π)|) | Hurt |
| Apply the generalized structural-compression reduction | Disjunctive ASP consistency · Incidence-graph treedepth | runtime lower bound: 22o(k) · poly(|at(Π)|) | Hurt |
| Apply the tree-decomposition compression reduction | Disjunctive ASP consistency · Pathwidth or cliquewidth of primal or incidence graph | runtime lower bound: 22o(k) · poly(|at(Π)|) | Hurt |
| Restrict the structural measure to bandwidth | Disjunctive ASP consistency · Bandwidth of primal or incidence graph | runtime lower bound: 22o(k) · poly(|at(Π)|) | Hurt |
| Restrict the structural measure to cutwidth | Disjunctive ASP consistency · Cutwidth of primal or incidence graph | runtime lower bound: 22o(k) · poly(|at(Π)|) | Hurt |
Surprising findings
- Vertex cover yields a polynomial kernel despite implicit subset-minimization of disjunctive ASP, unlike direct QBF encodings where vertex cover blows up.
- Disjunction can exponentially compress structural parameters, so disjunctive programs with simple structure are already hard.
Limitations
- Lower bounds rely on ETH; no practical evaluation of the reductions.
- Vertex cover kernel requires bounded rule size c; other measures remain hard.
- Results hold for normalized and fully tight programs; extension to non-tight programs is only sketched.
Experimental setup
Builds on: Lampis and Mitsou 2017 (QBF vertex cover) Hecher 2022 (treewidth lower bound for disjunctive ASP) Eiter and Gottlob 1995
Closest papers by meaning
- Characterizing Structural Hardness of Logic Programs: What Makes Cycles and Reachability Hard for Treewidth? (AAAI 2023 · similarity 0.92)
- Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard (AAAI 2021 · similarity 0.91)
- ApproxASP – a Scalable Approximate Answer Set Counter (AAAI 2022 · similarity 0.88)
- Exact ASP Counting with Compact Encodings (AAAI 2024 · similarity 0.87)
- A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming (AAAI 2024 · similarity 0.86)
- Recursive Aggregates as Intensional Functions in Answer Set Programming: Semantics and Strong Equivalence (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.