A fixed-parameter algorithm for the directed feedback vertex set problem

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)n^O(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4^k k! n^O(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.

REFERENCES

• 1: Vineet Bafna , Piotr Berman , Toshihiro Fujito, A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, SIAM Journal on Discrete Mathematics, v.12 n.3, p.289-297, Sept. 1999 [doi>10.1137/S0895480196305124]
• 2: Hans L. Bodlaender, On Linear Time Minor Tests and Depth First Search, Proceedings of the Workshop on Algorithms and Data Structures, p.577-590, August 17-19, 1989
• 3: 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.
• 4: 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.
• 5: Jianer Chen , Iyad A. Kanj , Weijia Jia, Vertex cover: further observations and further improvements, Journal of Algorithms, v.41 n.2, p.280-301, November 2001 [doi>10.1006/jagm.2001.1186]
• 6: 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.
• 7: 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.
• 8: 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.
• 9: R. Downey and M. Fellows, Fixed parameter intractability, Proc. 7th Annual Structural Complexity Conference, (1992), pp. 36--49.
• 10: Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
• 11: Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3]
• 12: R. Downey and M. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999.
• 13: G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica 20, (1998), pp. 151--174.
• 14: 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.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: Jiong Guo , Jens Gramm , Falk Hüffner , Rolf Niedermeier , Sebastian Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, v.72 n.8, p.1386-1396, December, 2006 [doi>10.1016/j.jcss.2006.02.001]
• 17: 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.
• 18: G. Gutin and A. Yeo, Some parameterized problems on digraphs, The Computer Journal, to appear.
• 19: F. Hüffner, R. Niedermeier, S. Wernicke, Techniques forPractical Fixed-Parameter Algorithms, The Computer Journal,51(1), 2008, pp. 7--25.
• 20: 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.
• 21: R. Karp Reducibility among combinatorial problems. in Complexity of Computer Computations, R. Miller and J. Thatcher, eds., Plenum Press, New York, pp. 85--103.
• 22: T. Leighton , S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, Proceedings of the [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, p.422-431, October 24-26, 1988 [doi>10.1109/SFCS.1988.21958]
• 23: C. Leiserson and J. Saxe, Retiming synchronous circuitry, Algorithmica 6, (1991), pp. 5--35.
• 24: Orna Lichtenstein , Amir Pnueli, Checking that finite state concurrent programs satisfy their linear specification, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-107, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318622]
• 25: R. Niedermeier, Invitation to fixed-parameter algorithms, iOxford Lecture Series in Mathematics and its Applications, volume31, 2006.
• 26: Venkatesh Raman , Saket Saurabh , C. R. Subramanian, Faster fixed parameter tractable algorithms for finding feedback vertex sets, ACM Transactions on Algorithms (TALG), v.2 n.3, p.403-415, July 2006 [doi>10.1145/1159892.1159898]
• 27: 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.
• 28: Venkatesh Raman , Saket Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science, v.351 n.3, p.446-458, 28 February 2006 [doi>10.1016/j.tcs.2005.10.010]
• 29: B. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Oper. Res. Lett. 32, (2004), pp. 299--301.
• 30: Abraham Siberschatz , Peter B. Galvin, Operating System Concepts, 4th Ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms

Keywords:
parameterized complexity