Parameterized algorithms for feedback set problems and their duals in tournaments

作     者：Raman, V Saurabh, S 

作者机构：Inst Math Sci Madras 600113 Tamil Nadu India 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 

年 卷 期：2006年第351卷第3期

页      面：446-458页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：tournaments feedback vertex set feedback arc set parameterized complexity 

摘      要：The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions. We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of k Vertices (arcs) that forms an acyclic directed subgraph of the graph? Our main results include: circle an O((2.4143)(k)n(omega) 1 algorithm for weighted feedback vertex set problem, and an O((2.415)(k)n(omega) algorithm for weighted feedback arc set problem in tournaments;circle an O((e2(k)/k)(k)k(2) + min{n lg n, n(2)}) algorithm for the dual of feedback vertex set problem (maxi m u m vertex i nd uced acycl ic graph) in oriented directed graphs, and an O(4(k)k + m) algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs. We also show that the dual of feedback vertex set is W[1]-hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems. (c) 2005 Elsevier B.V. All rights reserved.