A parameterized algorithm for mixed-cut

DOI10.1007/978-3-662-49529-2_50MaRDI QIDQ2802977zbMATH OpenOpenAlexFDO

Authors Ashutosh Rai, M. S. Ramanujan, Saket Saurabh

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05612

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: The classical Menger's theorem states that in any undirected (or directed) graph $G$, given a pair of vertices $s$ and $t$, the maximum number of vertex (edge) disjoint paths is equal to the minimum number of vertices (edges) needed to disconnect from $s$ and $t$. This min-max result can be turned into a polynomial time algorithm to find the maximum number of vertex (edge) disjoint paths as well as the minimum number of vertices (edges) needed to disconnect $s$ from $t$. In this paper we study a mixed version of this problem, called Mixed-Cut, where we are given an undirected graph $G$, vertices $s$ and $t$, positive integers $k$ and $l$ and the objective is to test whether there exist a $k$ sized vertex set $SsubseteqV(G)$ and an $l$ sized edge set $FsubseteqE(G)$ such that deletion of $S$ and $F$ from $G$ disconnects from $s$ and $t$. We start with a small observation that this problem is NP-complete and then study this problem, in fact a much stronger generalization of this, in the realm of parameterized complexity. In particular we study the Mixed-Multiway Cut-Uncut problem where along with a set of terminals $T$, we are also given an equivalence relation $mathcalR$ on $T$, and the question is whether we can delete at most $k$ vertices and at most $l$ edges such that connectivity of the terminals in the resulting graph respects $mathcalR$. Our main results is a fixed parameter algorithm for Mixed-Multiway Cut-Uncut using the method of recursive understanding introduced by Chitnis et al. (FOCS 2012).

Recommendations

• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• SOFSEM 2006: Theory and Practice of Computer Science
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset

Cited in

(11)

• Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• A generalized \(\alpha\)-cut
• The parameterized complexity landscape of two-sets cut-uncut
• Reducing CMSO model checking to highly connected graphs
• The parameterized complexity landscape of two-sets cut-uncut
• Two-sets cut-uncut on planar graphs
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• The complexity of mixed-connectivity
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• On structural parameterizations of the matching cut problem

This page was built for publication: A parameterized algorithm for mixed-cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802977)