On the maximum weight minimal separator

T. Hanaka, H.L. Bodlaender, T.C. van der Zanden, H. Ono

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
Place of PublicationCham
PublisherSpringer
Pages304-318
Number of pages15
ISBN (Print)9783319559100
DOIs
Publication statusPublished - 2017
Event14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Switzerland
Duration: 20 Apr 201722 Apr 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10185
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
CountrySwitzerland
CityBern
Period20/04/1722/04/17

Keywords

  • Minimal separator
  • Parameterized algorithm
  • Treewidth

Fingerprint Dive into the research topics of 'On the maximum weight minimal separator'. Together they form a unique fingerprint.

  • Cite this

    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 (pp. 304-318). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185). Cham: Springer. https://doi.org/10.1007/978-3-319-55911-7_22