Elimination Distance to Dominated Clusters

Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny · 2025

Read Elimination Distance to Dominated Clusters by Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21675.txt.

Introduction

Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny settle open questions in graph algorithms in a 2025 paper. Their problems ask whether deleting a few vertices, possibly in recursive layers, leaves a graph whose pieces each have a small dominating set. A recent paper classified most cases but left open whether one key parameter mix is tractable in the strong sense.

They give a uniform algorithm for both problem versions with the desired running-time shape. They also prove tractability under a different parameter, a structural index that can be far smaller than the older measure. A nearly full classification of the recursive version's complexity follows, with one hard base case still open.

Catalog record

CREATORNicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-21675

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Elimination Distance to Dominated Clusters Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny Abstract In the Dominated Cluster Deletion problem, we are given an undirected graph G G and integers k k and d d and the question is to decide whether there exists a set of at most k k vertices whose removal results in a graph in which each connected component has a dominating set of size at most d d . In the Elimination Distance to Dominated Clusters problem, we are again given an undirected graph G G and integers k k and d d and the question is to decide whether we can recursively delete vertices up to depth k k such that each remaining connected component has a dominating set of size at most d d . Bentert et al. [Bentert et al., MFCS 2024] recently provided an almost complete classification of the parameterized complexity of Dominated Cluster Deletion with respect to the parameters k k , d d , c c , and Δ \Delta , where c c and Δ \Delta are the degeneracy, and the maximum degree of the input graph, respectively. In particular, they provided a non-uniform algorithm with running time f ⁡ ( k , d ) ⋅ n 𝒪 ⁡ ( d ) f(k,d)\cdot n^{\mathcal{O}(d)} . They left as an open problem whether the problem is fixed-parameter tractable with respect to the parameter k + d + c k+d+c . We provide a uniform algorithm running in time f ⁡ ( k , d ) ⋅ n 𝒪 ⁡ ( d ) f(k,d)\cdot n^{\mathcal{O}(d)} for both Dominated Cluster Deletion and Elimination Distance to Dominated Clusters . We furthermore show that both problems are FPT when parameterized by k + d + ℓ k+d+\ell , where ℓ \ell is the semi-ladder index of the input graph, a parameter that is upper bounded and may be much smaller than the degeneracy c c , positively answering the open question of Bentert et al. We further complete the picture by providing an almost full classification for the parameterized complexity and kernelization complexity of Elimination Distance to Dominated Clusters . The one difficult base case that remains open is whether Treedepth (the case d = 0 d=0 ) is NP- hard on graphs of bounded maximum degree. University of Bremen, [email protected]://orcid.org/0000-0002-1740-7478 University of Bremen, [email protected]://orcid.org/0000-0002-6347-1198 Université Clermont Auvergne, Clermont Auvergne INP, LIMOS, CNRS, Clermont-Ferrand, [email protected]://orcid.org/0000-0002-4298-8876 ccs Mathematics of computing Graph algorithms ccs Theory of computation Fixed parameter tractability keywords Graph theory, Fixed-parameter algorithms, Dominated cluster deletion, Elimination distance † † runningauthor: N. Schirrmacher and S. Siebertz and A. Vigny † † copyright: Nicole Schirrmacher and Sebastian Siebertz and Alexandre Vigny † † funding: This paper is a part of the ANR-DFG project Unifying Theories for Multivariate Algorithms (UTMA), which has received funding from the German Research Foundation (DFG) with grant agreement No 446200270, and benefited from state aid managed by the ANR under France 2030 referenced ANR-23-IACL-0006. † † editors: John Q. Open and Joan R. Access † † event-title: 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) † † event-shorttitle: MFCS 2025 † † event-acronym: MFCS † † year: 2025 † † event-date: August 25 – 29, 2025 † † event-location: Warsaw, Poland † † series-volume: 42 † † articleno: XX 1 Introduction Assume that \mathcal{Q} is a graph problem that is hard to solve on general graphs but \mathscr{C} is a class of graphs where \mathcal{Q} can be solved efficiently. In many cases, we can also solve \mathcal{Q} efficiently on instances that are close to the instances of \mathscr{C} , say, on graphs that belong to \mathscr{C} after the deletion of a small number of vertices. Guo et al. [ 25 ] formalized this concept under the name distance from triviality . For example, the size of a minimum vertex cover is the distance to the class of edgeless graphs and the size of a minimum feedback vertex set is the distance to the class of acyclic graphs. Cluster Vertex Deletion is the problem to determine for a given graph and number k whether there exists a set of at most k vertices whose deletion results in a cluster graph , that is, a graph in which every connected component is a clique [ 5 , 34 ] . Many generalizations and special cases of Cluster Vertex Deletion have been studied. For example, one may require that each connected component in the resulting graph is an s -club (a graph of diameter at most s) [ 21 , 28 ] or an s -plex (a graph in which each vertex has degree at least n-s ) [ 26 , 35 ] . Note that the special case where each clique in the solution graph has to be of size one is again the Vertex Cover problem. Very recently, Bentert et al. [ 4 ] studied the following Dominated Cluster Deletion problem: Given a graph G and integer parameters k and d , does there exist a set S of at most k vertices such that each connected component of G-S can be dominated by at most d vertices? Bentert et al. provided an almost complete classification of the parameterized complexity and kernelization complexity of Dominated Cluster Deletion with respect to the parameters k , d , c , and \Delta , where c and \Delta are the degeneracy and the maximum degree of the input graph, respectively. They proved the following results: Dominated Cluster Deletion is para-NP -hard for parameters k+\Delta and d+\Delta , W[2] -hard for parameter k+d and admits a non-uniform algorithm with running time f(k,d)\cdot n^{\mathcal{O}(d)} , and is non-uniformly fixed-parameter tractable with respect to parameter k+d+\Delta . They left as an open problem whether the problem is fixed-parameter tractable with respect to the parameter k+d+c . They also showed that the problem does not admit a polynomial kernel even for d=1 with respect to the parameter k+c , or with respect to the parameter k+d+\Delta , unless \textsf{NP}\subseteq\textsf{coNP/poly} . A related measure is the elimination distance to a class \mathscr{C} , which measures the number of recursive deletions of vertices needed for a graph G to become a member of \mathscr{C} . Formally, a graph G has elimination distance 0 to \mathscr{C} if G\in\mathscr{C} , and otherwise elimination distance k+1 , if in every connected component of G , we can delete a vertex such that the resulting graph has elimination distance k to \mathscr{C} . Note that elimination distance to the class containing only the empty graph corresponds to the well-known measure treedepth . Elimination distance was introduced by Bulian and Dawar [ 10 ] in their study of the parameterized complexity of the graph isomorphism problem. Just as distance to triviality, but with more general applicability, elimination distance allows to lift algorithmic results from a base class to more general graph classes. For example, Bulian and Dawar [ 10 ] provided an FPT algorithm for the graph isomorphism problem parameterized by the elimination distance to the class \mathscr{C}_{d} of graphs with maximum degree bounded by d , for any fixed integer d . Hols et al. [ 27 ] proved the existence of polynomial

Read the complete text