arXiv:2611.13392 · v1

Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number

首次提交 2026-11-10 08:12

版本更新 2026-11-10 08:12

雷达观测 2026-11-11 11:04

摘要

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 $\ell$, Minimum Membership Dominating Set asks whether there is a dominating set $D$ such that every vertex in $G$ is dominated by at most $\ell$ vertices in $D$. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus $\ell$ 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 $σ\cup ρ$. 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\mathsf{an}(G)-6$ vertices, where $\mathsf{an}(G)$ denotes the asteroidal number of $G$, we show that Minimum Membership Dominating Set admits an XP algorithm parameterized solely by asteroidal number.

作者备注：Accepted for publication in IPEC2026