On the maximum weight minimal separator

Tesshu Hanaka; Hans L. Bodlaender; Tom C. Van Der Zanden; Hirotaka Ono

doi:10.1007/978-3-319-55911-7_22

On the maximum weight minimal separator

Tesshu Hanaka^*, Hans L. Bodlaender, Tom C. Van Der Zanden, Hirotaka Ono

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Downloads (Pure)

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 tw^O( ^tw) n-time deterministic algorithm based on tree decompositions. Moreover, we also propose an O^∗ (9^tw W²)-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 language	English
Title of host publication	Theory and Applications of Models of Computation
Subtitle of host publication	14th Annual Conference, TAMC 2017, Proceedings
Publisher	Springer
Pages	304-318
Number of pages	15
ISBN (Print)	9783319559100
DOIs	https://doi.org/10.1007/978-3-319-55911-7_22
Publication status	Published - 2017
Event	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Switzerland Duration: 20 Apr 2017 → 22 Apr 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10185 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Country/Territory	Switzerland
City	Bern
Period	20/04/17 → 22/04/17

Keywords

Minimal separator
Parameterized algorithm
Treewidth

Access to Document

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

MaximumFinal published version, 341 KBLicence: Taverne

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 LNCS). Springer. https://doi.org/10.1007/978-3-319-55911-7_22

Hanaka, Tesshu ; Bodlaender, Hans L. ; Van Der Zanden, Tom C. et al. / On the maximum weight minimal separator. Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Proceedings. Springer, 2017. pp. 304-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7ee57b51a9594d0986cc6fbab124c7eb,

title = "On the maximum weight minimal separator",

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",

author = "Tesshu Hanaka and Bodlaender, {Hans L.} and {Van Der Zanden}, {Tom C.} and Hirotaka Ono",

year = "2017",

doi = "10.1007/978-3-319-55911-7_22",

language = "English",

isbn = "9783319559100",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "304--318",

booktitle = "Theory and Applications of Models of Computation",

address = "Germany",

note = "14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

}

Hanaka, T, Bodlaender, HL, Van Der Zanden, TC & 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

On the maximum weight minimal separator. / Hanaka, Tesshu; Bodlaender, Hans L.; Van Der Zanden, Tom C. et al.
Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Proceedings. Springer, 2017. p. 304-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the maximum weight minimal separator

AU - Hanaka, Tesshu

AU - Bodlaender, Hans L.

AU - Van Der Zanden, Tom C.

AU - Ono, Hirotaka

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

PB - Springer

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

Y2 - 20 April 2017 through 22 April 2017

ER -

Hanaka T, Bodlaender HL, Van Der Zanden TC, Ono H. On the maximum weight minimal separator. In Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Proceedings. Springer. 2017. p. 304-318. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-55911-7_22

On the maximum weight minimal separator

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this