Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number
cs.DS
Submitted: 2026-11-10
Updated: 2026-11-10
Comments: Accepted for publication in IPEC2026
License: http://creativecommons.org/licenses/by/4.0/
The gist: The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs.
Terminology
Abstract
The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate whether this tractability extends to its variants with natural constraints. Specifically, we study the Minimum Membership Dominating Set problem and its generalization, the Min. (σ, ρ) -Dominating Set problem. Given a graph G and a positive integer, Minimum Membership Dominating Set asks whether there is a dominating set D such that every vertex in G is dominated by at most vertices in D. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus is W[1]-hard, demonstrating that even this natural constraint serves as a severe barrier to designing FPT algorithms. To complement this, we present an XP algorithm for the Min. (σ, ρ) -Dominating Set problem parameterized by asteroidal number plus μ, where σ and ρ are finite sets of non-negative integers and μ is the maximum value in σ ρ. Note that asteroidal number generalizes leafage to arbitrary graphs. Combining this algorithm with our structural bound that every graph G admits a dominating set such that no vertex is dominated by more than 7 (G)-6 vertices, where (G) denotes the asteroidal number of G, we show that Minimum Membership Dominating Set admits an XP algorithm parameterized solely by asteroidal number.
Sources
- On the hardness of recognizing graphs of small mim-width and its variants
- Algorithms for Minimum Membership Dominating Set Problem
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time