|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Parameterized Algorithm for Mixed Cut | | Ashutosh Rai
; M. S. Ramanujan
; Saket Saurabh
; | | Date: |
18 Sep 2015 | | 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 $S subseteq V(G)$ and an $l$ sized edge set $F
subseteq E(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 $mathcal{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 $mathcal{R}$. 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). | | Source: | arXiv, 1509.5612 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER