Balanced independent and dominating sets on colored interval graphs

DOI10.1007/978-3-030-67731-2_7zbMATH Open1490.68147arXiv2003.05289OpenAlexW3127735748MaRDI QIDQ831789FDOQ831789

Martin Nöllenburg, Guangping Li, Jan-Henrik Haunert, Fabian Klute, Sujoy Bhore

Publication date: 24 March 2022

Abstract: We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely $f$-Balanced Independent Set ($f$-BIS) and $f$-Balanced Dominating Set ($f$-BDS). Let $G=(V,E)$ be a vertex-colored interval graph with a color assignment function $gammacolonVightarrow1,ldots,k$ that maps all vertices in $G$ onto $k$ colors. A subset of vertices $SsubseteqV$ is called $f$-balanced if $S$ contains $f$ vertices from each color class. In the $f$-BIS and $f$-BDS problems, the objective is to compute an independent set or a dominating set that is $f$-balanced. We show that both problems are NP-complete even on proper interval graphs. For the $f$-BIS problem, we design two FPT algorithms, one parameterized by $(f,k)$ for interval graphs and the other parameterized by the vertex cover number for general graphs. Moreover, for an optimization variant of BIS on interval graphs, we show that a simple greedy approach achieves an approximation ratio of $2$.

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The maximum clique problem
• Algorithmic graph theory and perfect graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• On approximating the minimum independent dominating set
• A simplified NP-complete satisfiability problem
• Representation of a finite graph by a set of intervals on the real line
• Finding a Maximum Clique in an Arbitrary Graph
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Point labeling with sliding labels
• Approximation algorithms for maximum independent set of pseudo-disks
• Label placement by maximum independent set in rectangles
• Optimizing active ranges for consistent dynamic map labeling
• PTAS for geometric hitting set problems via local search
• Counting the number of independent sets in chordal graphs
• A linear kernel for planar red-blue dominating set
• Term Rewriting and Applications
• Algorithm and hardness results on liar's dominating set and \({k}\)-tuple dominating set
• Interval scheduling and colorful independent sets

This page was built for publication: Balanced independent and dominating sets on colored interval graphs

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