Cited By
View all- Bodlaender H(2012)Fixed-Parameter tractability of treewidth and pathwidthThe Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344250(196-227)Online publication date: 1-Jan-2012
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
Pages 987 - 1003
Abstract
The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper we improve the algorithmic analysis of both problems by proving a series of combinatorial results relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in $O(2^{15.11\cdot\sqrt{k}}+n^{2})$ and $O(2^{10.1\cdot\sqrt {k}}+n^{2})$ steps, respectively.
References
[1]
Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. 12, 219---234 (2000) (electronic)
[2]
Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2007). Lecture Notes in Comput. Sci., vol. 4393, pp. 320---331. Springer, Berlin (2007)
[3]
Bodlaender, H.L., Penninkx, E.: A linear kernel for planar feedback vertex set. In: Proceedings of the 3rd International Workshop on Exact and Parameterized Computation (IWPEC 2008). Lecture Notes in Comput. Sci., vol. 5018, pp. 160---171. Springer, Berlin (2008)
[4]
Bodlaender, H.L., Penninkx, E., Tan, R.B.: A linear kernel for the k-disjoint cycle problem on planar graphs. In: Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008). Lecture Notes in Comput. Sci., vol. 5369, pp. 306---317. Springer, Berlin (2008)
[5]
Bodlaender, H., Fomin, F., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.: (Meta) kernelization. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009) (2009)
[6]
Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188---1198 (2008)
[7]
Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4---5), 111---118 (1998)
[8]
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6), 866---893 (2005)
[9]
Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica 41(4), 245---267 (2005)
[10]
Dorn, F.: Dynamic programming and fast matrix multiplication. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Comput. Sci., vol. 4168, pp. 280---291. Springer, Berlin (2006)
[11]
Dorn, F.: Designing subexponential algorithms: problems, techniques & structures. PhD thesis, Department of Informatics, University of Bergen (2007)
[12]
Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005). Lecture Notes in Comput. Sci., vol. 3669, pp. 95---106. Springer, Berlin (2005)
[13]
Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming in H-minor-free graphs. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 631---640 (2008)
[14]
Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential parameterized algorithms. Comput. Sci. Rev. 2(1), 29---39 (2008)
[15]
Fernau, H., Juedes, D.: A geometric approach to parameterized algorithms for domination problems on planar graphs. In: Proceedings of the 29th International Symposium on Mathematical Foundations of Computer (MFCS 2004). Lecture Notes in Comput. Sci., vol. 3153, pp. 488---499. Springer, Berlin (2004)
[16]
Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Handbook of Combinatorial Optimization, Supplement Vol. A, pp. 209---258. Kluwer Academic, Dordrecht (1999)
[17]
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)
[18]
Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput. 36(2), 281---309 (2006) (electronic)
[19]
Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theory 51(1), 53---81 (2006)
[20]
Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293---307 (2008)
[21]
Goemans, M.X., Williamson, D.P.: Primal-dual approximation algorithms for feedback problems in planar graphs. In: Integer Programming and Combinatorial Optimization, Vancouver, BC, 1996. Lecture Notes in Comput. Sci., vol. 1084, pp. 147---161. Springer, Berlin (1996)
[22]
Goemans, M.X., Williamson, D.P.: Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica 18(1), 37---59 (1998)
[23]
Gu, Q.-P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n3) time. ACM Trans. Algorithms 4(3), 30:13 (2008)
[24]
Hicks, I.V.: Planar branch decompositions. I. The ratcatcher. INFORMS J. Comput. 17(4), 402---412 (2005)
[25]
Hicks, I.V.: Planar branch decompositions. II. The cycle method. INFORMS J. Comput. 17(4), 413---421 (2005)
[26]
Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Proceedings of the 28th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2002). Lecture Notes in Comput. Sci., vol. 2573, pp. 282---295. Springer, Berlin (2002)
[27]
Lin, H.-M., Jou, J.-Y.: On computing the minimum feedback vertex set of a directed graph by contraction operations. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 19(3), 295---307 (2000)
[28]
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)
[29]
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52(2), 153---190 (1991)
[30]
Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217---241 (1994)
[31]
Thomassé, S.: A quadratic kernel for feedback vertex set. In: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 115---119. Society for Industrial and Applied Mathematics, Philadelphia (2009)
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
Recommendations
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard ...
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 ...
Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization
A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2011 Springer Science+Business Media, LLC.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 August 2011
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Nov 2024
Other Metrics
Citations
Cited By
View all- Bodlaender H(2012)Fixed-Parameter tractability of treewidth and pathwidthThe Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344250(196-227)Online publication date: 1-Jan-2012
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in