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 k-coloring \gamma \colon V \rightarrow \{1,\ldots,k\} for some k \in \mathbb N . A subset of vertices S\subseteq 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 %DIFDELCMD < \NP%%% -complete even on proper interval graphs. For the BIS problem on interval graphs, we design two %DIFDELCMD < \FPT%%% \ algorithms, one parameterized by (f,k) and the other by the vertex cover number of G. Moreover, we present a 2-approximation algorithm for a slight variation of BIS on proper interval graphs .
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 \gamma \colon V \rightarrow \{1,\ldots,k\} that maps all vertices in G onto k colors . A subset of vertices S\subseteq 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 %DIFDELCMD < \NP%%% NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two %DIFDELCMD < \FPT%%% 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 .
R
f-Balanced Independent Set
f-Balanced Independent Set
R
f-Balanced Dominating Set
f-Balanced Dominating Set
R
k-coloring
color assignment function
R
for some k \in \mathbb N
that maps all vertices in G onto k colors
R
f-balanced
f-balanced
R
-complete
NP-complete
R
\
FPT
R
we present a 2-approximation algorithm for a slight variation
for an optimization variant
R
proper interval graphs
interval graphs, we present a polynomial time approximation scheme (PTAS) and an O(n\log n) time 2-approximation algorithm