Linear transformations between dominating sets in the TAR-model

DOI10.4230/LIPICS.ISAAC.2020.37MaRDI QIDQ6087209zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Alice Joffard, Paul Ouvrard

Publication date 14 November 2023

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

zbMATH Keywords

addition removalconnectivitydiameterdominating setsminorreconfigurationtreewidth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: Given a graph $G$ and an integer $k$, a token addition and removal ({sf TAR} for short) reconfiguration sequence between two dominating sets $D_{sfs}$ and $D_{sft}$ of size at most $k$ is a sequence $S=langle{D}_0=D_{sfs},D_{1}ldots,D_{e}ll=D_{sft}angle$ of dominating sets of $G$ such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than $k$. We first improve a result of Haas and Seyffarth, by showing that if $k=Gamma(G)+alpha(G)-1$ (where $Gamma(G)$ is the maximum size of a minimal dominating set and $alpha(G)$ the maximum size of an independent set), then there exists a linear {sf TAR} reconfiguration sequence between any pair of dominating sets. We then improve these results on several graph classes by showing that the same holds for $K_{ell}$-minor free graph as long as $kgeGamma(G)+O(ellsqrtlogell)$ and for planar graphs whenever $kgeGamma(G)+3$. Finally, we show that if $k=Gamma(G)+tw(G)+1$, then there also exists a linear transformation between any pair of dominating sets.

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An extremal function for contractions of graphs
• Connected \(k\)-dominating graphs
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• Homomorphiesätze für Graphen
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• Incremental optimization of independent sets under the reconfiguration framework
• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• The \(k\)-dominating graph
• The complexity of change
• The complexity of dominating set reconfiguration

Cited in

(3)

• Reconfiguration graphs for dominating sets
• TS-reconfiguration of dominating sets in circle and circular-arc graphs
• A survey on the parameterized complexity of reconfiguration problems

This page was built for publication: Linear transformations between dominating sets in the TAR-model

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