论文标题
红蓝色加权顶点盖的参数化算法
Parameterized Algorithms for Red-Blue Weighted Vertex Cover on Trees
论文作者
论文摘要
\ textproc {加权顶点盖}是广泛研究的NP完整问题的变体，\ textproc {cortex Cover}，其中给我们一个图形，$ g =（v，e，w）$，function $ w：v \ v \ rightArrow \ rightarrow \ rightarrow \ rightarrow \ m nathbb {q}^{q}^{q}^{+} $ and parameter and parameTer and parameter＆a parameter and parameter and parameTer＆a parameter＆a parameter＆a parameter＆a parameter $ k $ k $。目的是确定是否存在顶点盖，$ s $，以便$ \ sum_ {v \ in s} w（v）\ leq k $。在我们的工作中，我们首先研究了\ textproc {加权顶点盖}的硬度，然后通过$ l $和$ k $在参数化下检查此问题，其中$ l $是具有分数权重的顶点的数量。然后，我们在树上研究\ textProc {red-Blue加权顶点盖}问题。在这个问题中，我们给我们一棵树，$ t =（v，e，w）$，其中函数$ w：v \ rightArrow \ mathbb {q}^{+} $，a函数$ c：v \ rightArrow \ rightArrow \ r，b \ \} $和两个参数$ k $和$ k_r $。我们必须确定是否存在$ s $的顶点盖，以便$ \ sum_ {v \ in s} w（v）\ leq k $和$ \ sum _ {\ ordack {v \ in s \\ c（v）= r}}} = r}} w（v）w（v）我们通过应用不同的还原技术和有意义的参数化来解决这个问题。我们还研究了此问题的一些限制性版本。
\textproc{Weighted Vertex Cover} is a variation of an extensively studied NP-complete problem, \textproc{Vertex Cover}, in which we are given a graph, $G = (V,E,w)$, where function $w:V \rightarrow \mathbb{Q}^{+}$ and a parameter $k$. The objective is to determine if there exists a vertex cover, $S$, such that $\sum_{v \in S}w(v) \leq k$. In our work, we first study the hardness of \textproc{Weighted Vertex Cover} and then examine this problem under parameterization by $l$ and $k$, where $l$ is the number of vertices with fractional weights. Then, we study the \textproc{Red-Blue Weighted Vertex Cover} problem on trees in detail. In this problem, we are given a tree, $T=(V,E,w)$, where function $w:V \rightarrow \mathbb{Q}^{+}$, a function $c:V \rightarrow \{R,B\}$ and two parameters $k$ and $k_R$. We have to determine if there exists a vertex cover, $S$, such that $\sum_{v \in S}w(v) \leq k$ and $\sum_{\substack{v \in S\\ c(v) = R}}w(v) \leq k_R$. We tackle this problem by applying different reduction techniques and meaningful parameterizations. We also study some restrictive versions of this problem.
