Preventing Small \(\mathbf{(s,t)}\)-Cuts by Protecting Edges

We introduce and study Weighted Min \((s,t)\)-Cut Prevention, where we are given a graph \(G=(V,E)\) with vertices \(s\) and \(t\) and an edge cost function and the aim is to choose an edge set \(D\) of total cost at most \(d\) such that \(G\) has no \((s,t)\)-edge cut of capacity at most \(a\) that...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-07
Main Authors: Grüttemeier, Niels, Komusiewicz, Christian, Morawietz, Nils, Sommer, Frank
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Cost function
Graph theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce and study Weighted Min \((s,t)\)-Cut Prevention, where we are given a graph \(G=(V,E)\) with vertices \(s\) and \(t\) and an edge cost function and the aim is to choose an edge set \(D\) of total cost at most \(d\) such that \(G\) has no \((s,t)\)-edge cut of capacity at most \(a\) that is disjoint from \(D\). We show that Weighted Min \((s,t)\)-Cut Prevention is NP-hard even on subcubcic graphs when all edges have capacity and cost one and provide a comprehensive study of the parameterized complexity of the problem. We show, for example W[1]-hardness with respect to \(d\) and an FPT algorithm for \(a\).
ISSN:2331-8422