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

Created from the Publication Database of the Vienna University of Technology.