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

ABSTRACT

The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., 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 a set exists. It has been a well-known open problem in parameterized computation and complexity whether the DFVS problem is fixed-parameter tractable, that is, whether the problem can be solved in time f(k)n^O(1) for some function f. In this article, we develop new algorithmic techniques that result in an algorithm with running time 4^k k! n^O(1) for the DFVS problem. Therefore, we resolve this open problem.

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 with depth-first search, Journal of Algorithms, v.14 n.1, p.1-23, Jan. 1993 [doi>10.1006/jagm.1993.1001]
• 3: Bodlaender, H. 2007. A cubic kernel for feedback vertex set. In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lecture Notes in Computer Science, vol. 4393. Springer-Verlag, New York, 320--331.
• 4: Bodlaender, H., and Penninkx, E. 2008. A linear kernel for planar feedback vertex set. In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC 2008), Lecture Notes in Computer Science, vol. 5018. Springer-Verlag, New York, 160--171.
• 5: Chen, J., Fomin, F., Liu, Y., Lu, S., and Villanger, Y. 2007a. Improved algorithms for the feedback vertex set problems. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07), Lecture Notes in Computer Science, vol. 4619. Springer-Verlag, New York, 422--433.
• 6: 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]
• 7: Chen, J., Liu, Y., and Lu, S. 2007b. An improved parameterized algorithm for the minimum node multiway cut problem. In Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07), Lecture Notes in Computer Science, vol. 4619. Springer-Verlag, New York, 495--506.
• 8: Frank Dehne , Michael Fellows , Michael Langston , Frances Rosamond , Kim Stevens, An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertex Set Problem, Theory of Computing Systems, v.41 n.3, p.479-492, October 2007 [doi>10.1007/s00224-007-1345-z]
• 9: Downey, R., and Fellows, M. 1992. Fixed parameter intractability. In Proceedings of the 7th Annual Structural Complexity Conference. IEEE Computer Society Press, Los Alamitos, CA, 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: Downey, R., and Fellows, M. 1999. Parameterized Complexity. Springer-Verlag, New York.
• 12: Even, G., Naor, J., Schieber, B., and Sudan, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 151--174.
• 13: Gardarin, G., and Spaccapietra, S. 1976. Integrity of databases: A general lockout algorithm with deadlock avoidance. In Modeling in Data Base Management System, G, Nijsssen, Ed. North-Holland, Amsterdam, The Netherlands, 395--411.
• 14: 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
• 15: Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., and Wernicke, S. 2005. Improved fixed-parameter algorithms for two feedback set problems. In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS'05), Lecture Notes in Computer Science, vol. 3608. Springer-Verlag, New York, 158--168.
• 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: Gutin, G., and Yeo, A. 2008. Some parameterized problems on digraphs. Comput. J. 51, 363--371.
• 18: Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher, Eds. Plenum Press, New York, 85--103.
• 19: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 20: Leiserson, C., and Saxe, J. 1991. Retiming synchronous circuitry. Algorithmica 6, 5--35.
• 21: 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]
• 22: Reed, B., Smith, K., and Vetta, A. 2004. Finding odd cycle transversals. Oper. Res. Lett. 32, 299--301.
• 23: Schrijver, A. 2003. Combinatorial Optimization. Springer-Verlag, Berlin, Germany.
• 24: 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

General Terms:
Algorithms, Theory

Keywords:
Deadlock, feedback vertex set, parameterized computation