TY - GEN

T1 - On the maximum weight minimal separator

AU - Hanaka, T.

AU - Bodlaender, H.L.

AU - van der Zanden, T.C.

AU - Ono, H.

PY - 2017

Y1 - 2017

N2 - 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. In this paper, we consider finding a minimal s-t separator with maximum weight on a vertex-weighted graph. We first prove that this problem is NP-hard. Then, we propose an twO( tw) n-time deterministic algorithm based on tree decompositions. Moreover, we also propose an O∗ (9tw W2)-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.

AB - 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. In this paper, we consider finding a minimal s-t separator with maximum weight on a vertex-weighted graph. We first prove that this problem is NP-hard. Then, we propose an twO( tw) n-time deterministic algorithm based on tree decompositions. Moreover, we also propose an O∗ (9tw W2)-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.

KW - Minimal separator

KW - Parameterized algorithm

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85018372737&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-55911-7_22

DO - 10.1007/978-3-319-55911-7_22

M3 - Conference contribution

AN - SCOPUS:85018372737

SN - 9783319559100

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 304

EP - 318

BT - Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings

PB - Springer

CY - Cham

T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017

Y2 - 20 April 2017 through 22 April 2017

ER -