[Back]

A. Rai, M. S. Ramanujan, S. Saurabh:
"A Parameterized Algorithm for Mixed-Cut";
Talk: Latin American Theoretical Informatics Symposium, Ensenada, Mexico; 2016-04-11 - 2016-04-15; in: "Proceedings of LATIN 2016: Theoretical Informatics - 12th Latin American Symposium", (2016), ISBN: 978-3-662-49528-5; 672 - 685.

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 s from 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 S ⊆ V (G)
and an l sized edge set F ⊆ E(G) such that deletion of S and F from
G disconnects from s and t. Apart from studying a generalization of
classical problem, one of our main motivations for studying this problem
comes from the fact that this problem naturally arises as a subproblem
in the study of several graph editing (modification) problems. 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 R 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 R. Ourmain
result is a fixed parameter algorithm for Mixed Multiway Cut-Uncut
using the method of recursive understanding introduced by Chitnis
et al. (FOCS 2012).

http://publik.tuwien.ac.at/files/publik_256126.pdf