论文标题
节点连接增强问题的参数化算法
Parameterized algorithms for node connectivity augmentation problems
论文作者
论文摘要
图形$ g $是$ k $ out与节点$ s $连接的，如果它包含$ k $内部脱节$ sv $ path-与每个节点$ v $ s。 $ g $是$ k $连接的，如果是$ k $ - 与每个节点连接。在连接性增强问题中，目标是通过最低成本edge Edge设置$ J $增加图形$ g_0 =（v，e_0）$，这样$ g_0 \ cup j $的连接性高于$ g_0 $。在$ k $ - out连接性增强（$ k $ -oca）问题中，$ g_0 $是$（k-1）$ - 与$ s $相关，$ s $和$ g_0 \ cup j $应该是$ k $ - 与$ s $连接；在$ k $ - 连接性增强（$ k $ -ca）中问题$ g_0 $ is $（k-1）$ - 连接，$ g_0 \ cup j $应该为$ k $ - 连接。这些问题的参数化复杂性状态即使是$ k = 3 $和单位成本也开放。我们将证明$ K $ -OCA和$ 3 $ -CA可以在时间$ 9^p \ cdot n^{o（1）} $中解决，其中$ p $是最佳解决方案的大小。我们的论文是第一个显示$ k $ - 节点连接性增强问题的固定参数障碍性，高值为$ k $。我们还将考虑$（2，k）$ - 连接增强问题，其中$ g_0 $是$（k-1）$ - 边缘连接，$ g_0 \ cup j $应该是$ k $ - 边缘连接和$ 2 $连接的。我们将证明可以在$ 9^p \ cdot n^{o（1）} $的时间内解决此问题，并且单位费用约为$ 1.892 $。
A graph $G$ is $k$-out-connected from its node $s$ if it contains $k$ internally disjoint $sv$-paths to every node $v$; $G$ is $k$-connected if it is $k$-out-connected from every node. In connectivity augmentation problems the goal is to augment a graph $G_0=(V,E_0)$ by a minimum costs edge set $J$ such that $G_0 \cup J$ has higher connectivity than $G_0$. In the $k$-Out-Connectivity Augmentation ($k$-OCA) problem, $G_0$ is $(k-1)$-out-connected from $s$ and $G_0 \cup J$ should be $k$-out-connected from $s$; in the $k$-Connectivity Augmentation ($k$-CA) problem $G_0$ is $(k-1)$-connected and $G_0 \cup J$ should be $k$-connected. The parameterized complexity status of these problems was open even for $k=3$ and unit costs. We will show that $k$-OCA and $3$-CA can be solved in time $9^p \cdot n^{O(1)}$, where $p$ is the size of an optimal solution. Our paper is the first that shows fixed parameter tractability of a $k$-node-connectivity augmentation problem with high values of $k$. We will also consider the $(2,k)$-Connectivity Augmentation problem where $G_0$ is $(k-1)$-edge-connected and $G_0 \cup J$ should be both $k$-edge-connected and $2$-connected. We will show that this problem can be solved in time $9^p \cdot n^{O(1)}$, and for unit costs approximated within $1.892$.
