### 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^{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.

Original language | English |
---|---|

Title of host publication | Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings |

Place of Publication | Cham |

Publisher | Springer |

Pages | 304-318 |

Number of pages | 15 |

ISBN (Print) | 9783319559100 |

DOIs | |

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 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

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

Country | Switzerland |

City | Bern |

Period | 20/04/17 → 22/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

*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