On the maximum weight minimal separator

Given an undirected and connected graph G = ( V, E ) and two vertices s, t ∈ V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper subset of S separates s and t. Moreover, we say that a set S is a minimal separator of G if S is a minimal s-t separator for some s and t. In this paper, we consider finding a minimal (s-t) separator with maximum weight on a vertex-weighted graph. We first prove that these problems are NP-hard. On the other hand, we give an O ⁎ ( tw O ( tw ) ) -time deterministic algorithm based on tree decompositions where O ⁎ is the order notation omitting the polynomial factor of n. Moreover, we improve the algorithm by using the Rank-Based approach and the running time is O ⁎ ( 38 ⋅ 2 ω ) tw. Finally, we give an O ⁎ ( 9 tw ⋅ W 2 ) -time randomized algorithm to determine whether there exists a minimal (s-t) separator where W is its weight and tw is the treewidth of G.

Authors

• Tesshu Hanaka Kyushu University
• Hans L. Bodlaender
• Tom C. van der Zanden
• Hirotaka Ono Nagoya University

Keywords

• Parameterized algorithm
• Minimal separator
• Treewidth