|国家预印本平台
首页|Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

来源:Arxiv_logoArxiv
英文摘要

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$.

Mark Jones、Gregory Gutin、Anders Yeo、Robert Crowston

计算技术、计算机技术

Mark Jones,Gregory Gutin,Anders Yeo,Robert Crowston.Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments[EB/OL].(2011-06-22)[2025-08-02].https://arxiv.org/abs/1106.4454.点此复制

评论