Abstract
We study the parameterized complexity of the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (disjoint-fvs), which finds a disjoint feedback vertex set of size k when a feedback vertex set of a graph is given. We show that disjoint-fvs admits a small kernel, and can be solved in polynomial time when the graph has a special structure that is closely related to the maximum genus of the graph. We then propose a simple branch-and-search process on disjoint-fvs, and introduce a new branch-and-search measure. The branch-and-search process effectively reduces a given graph to a graph with the special structure, and the new measure more precisely evaluates the efficiency of the branch-and-search process. These algorithmic, combinatorial, and topological structural studies enable us to develop an O(3.83k kn 2) time parameterized algorithm for the general fvs problem, improving the previous best algorithm of time O(5k k n 2) for the problem.
Supported in part by the US NSF under the Grants CCF-0830455 and CCF-0917288.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. 12, 219–234 (2000)
Bodlaender, H.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59–68 (1994)
Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set New Measure and New Structures (manuscript, 2010)
Chen, J.: Minimum and maximum imbeddings. In: Gross, J., Yellen, J. (eds.) The Handbook of Graph Theory, pp. 625–641. CRC Press, Boca Raton (2003)
Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for the feedback vertex set problems. Journal of Computer and System Sciences 74, 1188–1198 (2008)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company (2001)
Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An O(2O(k) n 3) fpt algorithm for the undirected feedback vertex set problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 859–869. Springer, Heidelberg (2005)
Downey, R., Fellows, M.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191–225. Cambridge University Press, Cambridge (1992)
Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)
Festa, P., Pardalos, P., Resende, M.: Feedback set problems. In: Handbook of Combinatorial Optimization, vol. A(suppl.), pp. 209–258. Kluwer Acad. Publ., Dordrecht (1999)
Fomin, F., Gaspers, S., Pyatkin, A.: Finding a minimum feedback vertex set in time O(1.7548n). In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 184–191. Springer, Heidelberg (2006)
Furst, M., Gross, J., McGeoch, L.: Finding a maximum-genus graph imbedding. Journal of the ACM 35(3), 523–534 (1988)
Gabow, H., Stallmann, M.: Efficient algorithms for graphic matroid intersection and parity. In: Brauer, W. (ed.) ICALP 1985. LNCS, vol. 194, pp. 210–220. Springer, Heidelberg (1985)
Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)
Kanj, I., Pelsmajer, M., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 235–247. Springer, Heidelberg (2004)
Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Li, D., Liu, Y.: A polynomial algorithm for finding the minimul feedback vertex set of a 3-regular simple graph. Acta Mathematica Scientia 19(4), 375–381 (1999)
Lovász, L.: The matroid matching problem. In: Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis János Bolyai, Szeged, Hungary (1978)
Raman, V., Saurabh, S., Subramanian, C.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Trans. Algorithms 2(3), 403–415 (2006)
Raman, V., Saurabh, S., Subramanian, C.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 241–248. Springer, Heidelberg (2002)
Razgon, I.: Exact computation of maximum induced forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 160–171. Springer, Heidelberg (2006)
Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004)
Silberschatz, A., Galvin, P.: Operating System Concepts, 4th edn. Addison-Wesley, Reading (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cao, Y., Chen, J., Liu, Y. (2010). On Feedback Vertex Set New Measure and New Structures. In: Kaplan, H. (eds) Algorithm Theory - SWAT 2010. SWAT 2010. Lecture Notes in Computer Science, vol 6139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13731-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-13731-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13730-3
Online ISBN: 978-3-642-13731-0
eBook Packages: Computer ScienceComputer Science (R0)