The parameterized complexity of the equidomination problem

DOI10.1007/978-3-319-68705-6_31MaRDI QIDQ1687940zbMATH OpenOpenAlexFDO

Authors Oliver Schaudt, Fabian Senger

Publication date 4 January 2018

Full work available at URL https://arxiv.org/abs/1705.05599

zbMATH Keywords

equidominating graphhereditary propertykernelizationminimal dominating setparameterized complexity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Abstract: A graph $G=(V,E)$ is called equidominating if there exists a value $tinmathbbN$ and a weight function $omega:VightarrowmathbbN$ such that the total weight of a subset $DsubseteqV$ is equal to $t$ if and only if $D$ is a minimal dominating set. To decide whether or not a given graph is equidominating is referred to as the Equidomination problem. In this paper we show that two parameterized versions of the Equidomination problem are fixed-parameter tractable: the first parameterization considers the target value $t$ leading to the Target-$t$ Equidomination problem. The second parameterization allows only weights up to a value $k$, which yields the $k$-Equidomination problem. In addition, we characterize the graphs whose every induced subgraph is equidominating. We give a finite forbidden induced subgraph characterization and derive a fast recognition algorithm.

Recommendations

• Equivalence dominating sets in graphs
• Equivalence domination in graphs
• Equi independent equitable dominating sets in graphs
• Equivalence domination number of a tree
• Degree equitable domination on graphs

Cited in

(2)

• A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
• scientific article; zbMATH DE number 1143806 (Why is no real title available?)

This page was built for publication: The parameterized complexity of the equidomination problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1687940)