On the maximum weight minimal separator
Files
Publication date
2017
Authors
Hanaka, Tesshu
Bodlaender, Hans
van der Zanden, Tom C.
Ono, Hirotaka
Editors
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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.
Keywords
Minimal separator, Parameterized algorithm, Treewidth, Taverne, Theoretical Computer Science, General Computer Science
Citation
Hanaka, T, Bodlaender, H L, Van Der Zanden, T C & Ono, H 2017, On the maximum weight minimal separator. in Theory and Applications of Models of Computation : 14th Annual Conference, TAMC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10185 LNCS, Springer, pp. 304-318, 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, Switzerland, 20/04/17. https://doi.org/10.1007/978-3-319-55911-7_22, conference