2024/05/17 by Dishant Goyal, Ashwin Jacob, Goyal, Dishant +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2405.10556
openalex publication_date 2024/05/17 · openalex created_date 2024/05/21 · openalex updated_date 2026/07/28
We consider structural parameterizations of the fundamental Dominating Set problem and its variants in the parameter ecology program. We give improved FPT algorithms and lower bounds under well-known conjectures for dominating set in graphs that are k vertices away from a cluster graph or a split graph. These are graphs in which there is a set of k vertices (called the modulator) whose deletion results in a cluster graph or a split graph. We also call k as the deletion distance (to the appropriate class of graphs). When parameterized by the deletion distance k to cluster graphs - we can find a minimum dominating set (DS) in 3k nO(1)-time. Within the same time, we can also find a minimum independent dominating set (IDS) or a minimum dominating clique (DC) or a minimum efficient dominating set (EDS) or a minimum total dominating set (TDS). We also show that most of these variants of dominating set do not have polynomial sized kernel. Additionally, we show that when parameterized by the deletion distance k to split graphs - IDS can be solved in 2k nO(1)-time and EDS can be solved in 3k/2nO(1).