论文标题
寻找最短的非分离和非隔离路径
Finding shortest non-separating and non-disconnecting paths
论文作者
论文摘要
对于连接的图形$ g =（v，e）$和$ s，t \ in v $，一个非分离的$ s $ - $ t $路径是$ s $ s $和$ t $之间的路径$ p $，因此$ p $的一组顶点不分开$ g $，也就是说，$ g-v（p）$已连接。如果连接$ g-e（p）$，则$ s $ - $ t $路径是无关的。发现最短的非分离和非隔离路径的问题都是NP-HARD。在本文中，我们从参数化复杂性的角度考虑了问题。我们表明，找到最多$ k $长度长度的非分离$ s $ -s $ - $ t $的问题是$ k $参数化的，而非案件的对应物是固定参数可通过$ k $参数化的固定参数。我们还考虑了几类图表上最短的非分离路径问题，并表明即使在两部分图，拆分图和平面图上，此问题也是NP-HARD。至于积极的结果，如果$ k $是$ k $是$ s $和$ t $之间的最短路径距离，则最短的非分离路径问题是由$ k $在平面图上的固定参数处理和可在弦图上解决的多项式时间的参数。
For a connected graph $G = (V, E)$ and $s, t \in V$, a non-separating $s$-$t$ path is a path $P$ between $s$ and $t$ such that the set of vertices of $P$ does not separate $G$, that is, $G - V(P)$ is connected. An $s$-$t$ path is non-disconnecting if $G - E(P)$ is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating $s$-$t$ path of length at most $k$ is W[1]-hard parameterized by $k$, while the non-disconnecting counterpart is fixed-parameter tractable parameterized by $k$. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is fixed-parameter tractable parameterized by $k$ on planar graphs and polynomial-time solvable on chordal graphs if $k$ is the shortest path distance between $s$ and $t$.
