Balanced independent and dominating sets on colored interval graphs

DOI10.1007/978-3-030-67731-2_7MaRDI QIDQ831789zbMATH OpenOpenAlexFDO

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

Publication date 24 March 2022

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)

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$.

Recommendations

• Balanced connected subgraph problem in geometric intersection graphs
• Exact algorithms for intervalizing colored graphs
• On the sum coloring problem on interval graphs
• Maximum colorful independent sets in vertex-colored graphs
• scientific article; zbMATH DE number 1588325

Cites work

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

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)