Multicut is FPT

Details Multicut is FPT Multicut is FPT

2010-10-25

arxiv.org/abs/1010.5197v3

Computer Science

Data Structures and Algorithms

Scientific paper

Let $G=(V,E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices in $V$ called \emph{requests}. A \emph{multicut} is a subset $F$ of $E$ such that every request $xy$ of $R$ is cut by $F$, \i.e. every $xy$-path of $G$ intersects $F$. We show that there exists an $O(f(k)n^c)$ algorithm which decides if there exists a multicut of size at most $k$. In other words, the \M{} problem parameterized by the solution size $k$ is Fixed-Parameter Tractable. The proof extends to vertex multicuts.

Affiliated with

Also associated with

No associations

Rating

Multicut is FPT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multicut is FPT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicut is FPT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-94471