Balanced Independent and Dominating Sets on Colored Interval Graphs

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

doi:10.1007/978-3-030-67731-2_7

Balanced Independent and Dominating Sets on Colored Interval Graphs

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 an interval graph with a color assignment function γ:V→{1,…,k} that maps all vertices in G onto k colors. A subset of vertices S⊆V 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 BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an O(nlogn) time 2-approximation algorithm.

Original language	English
Title of host publication	SOFSEM 2021: Theory and Practice of Computer Science
Subtitle of host publication	47th International Conference on Current Trends in Theory and Practice of Computer Science
Editors	Tomáš Bureš, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdzinski, Claus Pahl, Florian Sikora, Prudence W. Wong
Publisher	Springer
Pages	89-103
Number of pages	15
ISBN (Electronic)	978-3-030-67731-2
ISBN (Print)	978-3-030-67730-5
DOIs	https://doi.org/10.1007/978-3-030-67731-2_7
Publication status	Published - 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12607 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-67731-2_7

Bhore2021_Chapter_BalancedIndependentAndDominatiFinal published version, 418 KBLicence: Taverne

Cite this

Bhore, S., Haunert, J.-H., Klute, F., Li, G., & Nöllenburg, M. (2021). Balanced Independent and Dominating Sets on Colored Interval Graphs. In T. Bureš, R. Dondi, J. Gamper, G. Guerrini, T. Jurdzinski, C. Pahl, F. Sikora, & P. W. Wong (Eds.), SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current Trends in Theory and Practice of Computer Science (pp. 89-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12607 LNCS). Springer. https://doi.org/10.1007/978-3-030-67731-2_7

Bhore, Sujoy ; Haunert, Jan-Henrik ; Klute, Fabian et al. / Balanced Independent and Dominating Sets on Colored Interval Graphs. SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current Trends in Theory and Practice of Computer Science. editor / Tomáš Bureš ; Riccardo Dondi ; Johann Gamper ; Giovanna Guerrini ; Tomasz Jurdzinski ; Claus Pahl ; Florian Sikora ; Prudence W. Wong. Springer, 2021. pp. 89-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{00dcd444d3cc4ad9890793f33867b681,

title = "Balanced Independent and Dominating Sets on Colored Interval Graphs",

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 an interval graph with a color assignment function γ:V→{1,…,k} that maps all vertices in G onto k colors. A subset of vertices S⊆V 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 BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an O(nlogn) time 2-approximation algorithm.",

author = "Sujoy Bhore and Jan-Henrik Haunert and Fabian Klute and Guangping Li and Martin N{\"o}llenburg",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-67731-2_7",

language = "English",

isbn = "978-3-030-67730-5",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "89--103",

editor = "Tom{\'a}{\v s} Bure{\v s} and Riccardo Dondi and Johann Gamper and Giovanna Guerrini and Tomasz Jurdzinski and Claus Pahl and Florian Sikora and Wong, {Prudence W.}",

booktitle = "SOFSEM 2021: Theory and Practice of Computer Science",

}

Bhore, S, Haunert, J-H, Klute, F, Li, G & Nöllenburg, M 2021, Balanced Independent and Dominating Sets on Colored Interval Graphs. in T Bureš, R Dondi, J Gamper, G Guerrini, T Jurdzinski, C Pahl, F Sikora & PW Wong (eds), SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current Trends in Theory and Practice of Computer Science. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12607 LNCS, Springer, pp. 89-103. https://doi.org/10.1007/978-3-030-67731-2_7

Balanced Independent and Dominating Sets on Colored Interval Graphs. / Bhore, Sujoy; Haunert, Jan-Henrik; Klute, Fabian et al.
SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current Trends in Theory and Practice of Computer Science. ed. / Tomáš Bureš; Riccardo Dondi; Johann Gamper; Giovanna Guerrini; Tomasz Jurdzinski; Claus Pahl; Florian Sikora; Prudence W. Wong. Springer, 2021. p. 89-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12607 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Balanced Independent and Dominating Sets on Colored Interval Graphs

AU - Bhore, Sujoy

AU - Haunert, Jan-Henrik

AU - Klute, Fabian

AU - Li, Guangping

AU - Nöllenburg, Martin

PY - 2021

Y1 - 2021

N2 - 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 an interval graph with a color assignment function γ:V→{1,…,k} that maps all vertices in G onto k colors. A subset of vertices S⊆V 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 BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an O(nlogn) time 2-approximation algorithm.

AB - 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 an interval graph with a color assignment function γ:V→{1,…,k} that maps all vertices in G onto k colors. A subset of vertices S⊆V 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 BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an O(nlogn) time 2-approximation algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85101517856&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-67731-2_7

DO - 10.1007/978-3-030-67731-2_7

M3 - Conference contribution

SN - 978-3-030-67730-5

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 89

EP - 103

BT - SOFSEM 2021: Theory and Practice of Computer Science

A2 - Bureš, Tomáš

A2 - Dondi, Riccardo

A2 - Gamper, Johann

A2 - Guerrini, Giovanna

A2 - Jurdzinski, Tomasz

A2 - Pahl, Claus

A2 - Sikora, Florian

A2 - Wong, Prudence W.

PB - Springer

ER -

Bhore S, Haunert JH, Klute F, Li G, Nöllenburg M. Balanced Independent and Dominating Sets on Colored Interval Graphs. In Bureš T, Dondi R, Gamper J, Guerrini G, Jurdzinski T, Pahl C, Sikora F, Wong PW, editors, SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current Trends in Theory and Practice of Computer Science. Springer. 2021. p. 89-103. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-67731-2_7

Balanced Independent and Dominating Sets on Colored Interval Graphs

Abstract

Publication series

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this