[Back]

S. Bhore, J. Haunert, F. Klute, G. Li, M. Nöllenburg:
"Balanced Independent and Dominating Sets on Colored Interval Graphs";
Talk: International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Bozen, Italy; 2021-01-25 - 2021-01-29; in: "SOFSEM 2021: Theory and Practice of Computer Science", Springer, LNCS 12607 (2021), ISBN: 978-3-030-67730-5; 89 - 103.

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(n log n) time 2-approximation algorithm.

http://dx.doi.org/10.1007/978-3-030-67731-2_7