Let A and B be disjoint, non-adjacent vertex-sets in an undirected, connected graph G, whose vertices are associated with positive weights. We address the problem of identifying a minimum-weight subset of vertices \(S\subseteq \texttt {V}(G)\) that, when removed, disconnects A from B while preserving the internal connectivity of both A and B. We call such a subset of vertices a connectivity-preserving, or safe minimum A, B-separator. Deciding whether a safe A, B-separator exists is NP-hard by reduction from the 2-disjoint connected subgraphs problem [15], and remains NP-hard even for restricted graph classes that include planar graphs [14], and \(P_\ell \) -free graphs if \(\ell \ge 5\)  [15]. In this work, we show that if G is AT-free then in polynomial time we can find a safe A, B-separator of minimum weight, or establish that no safe A, B-separator exists.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Connectivity-Preserving Minimum Separator in AT-Free Graphs

  • Batya Kenig

摘要

Let A and B be disjoint, non-adjacent vertex-sets in an undirected, connected graph G, whose vertices are associated with positive weights. We address the problem of identifying a minimum-weight subset of vertices \(S\subseteq \texttt {V}(G)\) that, when removed, disconnects A from B while preserving the internal connectivity of both A and B. We call such a subset of vertices a connectivity-preserving, or safe minimum A, B-separator. Deciding whether a safe A, B-separator exists is NP-hard by reduction from the 2-disjoint connected subgraphs problem [15], and remains NP-hard even for restricted graph classes that include planar graphs [14], and \(P_\ell \) -free graphs if \(\ell \ge 5\)  [15]. In this work, we show that if G is AT-free then in polynomial time we can find a safe A, B-separator of minimum weight, or establish that no safe A, B-separator exists.