论文标题
在彩色间隔图上平衡独立和主导集
Balanced Independent and Dominating Sets on Colored Interval Graphs
论文作者
论文摘要
我们研究了两个新版本的独立和主导设置的问题，上面是顶点颜色的间隔图，即$ f $平衡的独立套件（$ f $ -bis）和$ f $ f $ - 平衡的主导套装（$ f $ -bds）。令$ g =（v，e）$是带有颜色分配功能$γ\ colon v \ rightarrow \ rightarrow \ {1，\ ldots，k \} $的顶点色的间隔图，将$ g $中的所有顶点映射到$ k $ colors。顶点$ S \ subseteq v $的子集称为$ f $ - 平衡，如果$ s $包含每个颜色类中的$ f $ vertices。在$ f $ bis和$ f $ -bds的问题中，目标是计算独立集或$ f $ bamborated的独立组。我们表明，即使在适当的间隔图上，这两个问题都是NP完整的。对于$ f $ bis问题，我们设计了两个FPT算法，一种由$（f，k）$用于间隔图的参数，另一个由一般图的顶点封面编号进行了参数。此外，对于在间隔图上的优化bis的优化变体，我们表明一种简单的贪婪方法达到了$ 2 $的近似值。
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 $γ\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 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$.
