Jianer Chen
ABSTRACT
The (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in G or report that no such set exists. Whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)nO(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4k k! nO(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.
- V. Bafna, P. Berman, and T. Fujito, A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J. Discrete Math. 12, (1999), pp. 289--297. Google Scholar
Digital Library
- H. Bodlaender, On linear time minor tests and depth-first search, Proc. 1st Workshop on Algorithms and Data Structures (WADS'89), (1989), pp. 577--590. Google ScholarDigital Library
- H. Bodlaender, A Cubic Kernel for Feedback Vertex Set, Proc. STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, 2007,pp. 320--331. Google ScholarDigital Library
- J. Chen, F. Fomin, Y. Liu, S. Lu, and Y. Villanger, Improved algorithms for the feedback vertex set problems, Proc. 10th Workshop on Algorithms and Data Structures, (WADS'07), Lecture Notes in Computer Science 4619, (2007), pp. 422--433. Google ScholarDigital Library
- J. Chen, I. Kanj, and W. Jia, Vertex cover: further observations and further improvements, Journal of Algorithms 41, (2001), pp. 280--301. Google ScholarDigital Library
- J. Chen, Y. Liu, and S. Lu, An improved parameterized algorithm for the minimum node multiway cut problem, Proc. 10th Workshop on Algorithms and Data Structures, (WADS'07), Lecture Notes in Computer Science 4619, (2007), pp. 495--506. Google ScholarDigital Library
- F. Dehne, M. Fellows, M. Langston, F. Rosamond, and K. Stevens, An $O(2^O(k) n^3)$ fpt algorithm for the undirected feedback vertex set problem, Proc. 11th International Computing and Combinatorics Conference (COCOON'05), Lecture Notes in Computer Science 3595, (2005), pp. 859--869.Google ScholarCross Ref
- M. Dom, J. Guo, F. Hüffner, R. Niedermeier, and A. Truß, Fixed-parameter tractability results for feedback set problems in tournaments, Proc. 6th Conference on Algorithms and Complexity (CIAC'06), Lecture Notes in Computer Science 3998, (2006), pp. 320--331. Google ScholarDigital Library
- R. Downey and M. Fellows, Fixed parameter intractability, Proc. 7th Annual Structural Complexity Conference, (1992), pp. 36--49.Google ScholarCross Ref
- R. Downey and M. Fellows, Fixed-parameter tractability and completeness I: Basic Results, SIAM J. Comput. 24, (1995), pp. 873--921. Google ScholarDigital Library
- R. Downey and M. Fellows, Fixed-parameter tractability and completeness II: on completeness for $W{1}$, Theoret. Computer Sci. 141, (1995), pp. 109--131. Google ScholarDigital Library
- R. Downey and M. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999. Google ScholarCross Ref
- G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica 20, (1998), pp. 151--174.Google ScholarCross Ref
- G. Gardarin and S. Spaccapietra, Integrity of databases: a general lockout algorithm with deadlock avoidance, in Modeling in Data Base Management System, G. Nijsssen, ed., North-Holland, Amsterdam, (1976), pp. 395--411.Google Scholar
- M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979. Google ScholarDigital Library
- J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, J. Comput. Syst. Sci. 72, (2006), pp. 1386--1396. Google ScholarDigital Library
- J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, Improved fixed-parameter algorithms for two feeback set problems, Proc. 9th Workshop on Algorithms and Data Structures (WADS'05), Lecture Notes in Computer Science 3608, (2005), pp. 158--168. Google ScholarDigital Library
- G. Gutin and A. Yeo, Some parameterized problems on digraphs, The Computer Journal, to appear. Google ScholarDigital Library
- F. Hüffner, R. Niedermeier, S. Wernicke, Techniques forPractical Fixed-Parameter Algorithms, The Computer Journal,51(1), 2008, pp. 7--25.Google ScholarCross Ref
- I. Kanj, M. Pelsmajer, and M. Schaefer, Parameterized algorithms for feedback vertex set, Proc. 1st International Workshop on Parameterized and Exact Computation (IWPEC'04), Lecture Notes in Computer Science 3162, (2004), pp. 235--247.Google ScholarCross Ref
- R. Karp Reducibility among combinatorial problems. in Complexity of Computer Computations, R. Miller and J. Thatcher, eds., Plenum Press, New York, pp. 85--103.Google Scholar
- T. Leighton and S. Rao, An approximation max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms, Proc. 29th IEEE Symp. on Foundations of Computer Science (FOCS'88), (1988), pp. 422--431. Google ScholarDigital Library
- C. Leiserson and J. Saxe, Retiming synchronous circuitry, Algorithmica 6, (1991), pp. 5--35.Google ScholarDigital Library
- O. Lichtenstein and A. Pnueli, Checking that finite state concurrent programs satisfy their linear specification. Proc. 12th ACM Symp. Principles of Prog. Languages, (1985), pp. 97--107. Google ScholarDigital Library
- R. Niedermeier, Invitation to fixed-parameter algorithms, iOxford Lecture Series in Mathematics and its Applications, volume31, 2006.Google Scholar
- V. Raman, S. Saurabh, and C. Subramanian, Faster fixed parameter tractable algorithms for finding feedback vertex sets, ACM Trans. Algorithms 2, (2006), pp. 403--415. Google ScholarDigital Library
- V. Raman and S. Saurabh, Parameterized complexity of directed feedback set problems in tournaments, Proc. 8th Workshop on Algorithms and Data Structures (WADS'03), Lecture Notes in Computer Science 2748, (2003), pp. 484--492.Google ScholarCross Ref
- V. Raman and S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments. Theoretical Computer Science 351, (2006), pp. 446--458. Google ScholarDigital Library
- B. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Oper. Res. Lett. 32, (2004), pp. 299--301. Google ScholarDigital Library
- A. Silberschatz and P. Galvin, Operating System Concepts, 4th ed., Addison Wesley, Reading, MA, 1994. Google ScholarDigital Library
Index Terms
- A fixed-parameter algorithm for the directed feedback vertex set problem
Recommendations
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Given a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of ...
Directed subset feedback vertex set is fixed-parameter tractable
ICALP'12: Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part IGiven a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. Bodlaender (WG '91) gave the first fixed-parameter algorithm for FVS in undirected graphs. The ...
Simultaneous Feedback Vertex Set: A Parameterized Perspective
For a family F of graphs, a graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex ...
Comments