Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

Details Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

2011-06-22

arxiv.org/abs/1106.4454v2

Computer Science

Data Structures and Algorithms

Scientific paper

In the problem {\sc Min-DESC}, we are given a digraph $D$ and an integer $k$, and asked if there exists a set $A'$ of at most $k$ arcs in $D$, such that if we remove the arcs of $A'$, in the resulting digraph every strong component is Eulerian. {\sc Min-DESC} is NP-hard; Cechl\'{a}rov\'{a} and Schlotter (IPEC 2010) asked if the problem is fixed-parameter tractable when parameterized by $k$. We consider the subproblem of{\sc Min-DESC} when $D$ is a tournament. We show that this problem is fixed-parameter tractable with respect to $k$.

Affiliated with

Also associated with

No associations

Rating

Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments 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 Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206749