Abstract
Preprocessing by data reduction is a simple but powerful technique used for practically solving different network problems. A number of empirical studies shows that a set of reduction rules for solving Dominating Set problems introduced by Alber, Fellows & Niedermeier leads efficiently to optimal solutions for many realistic networks. Despite of the encouraging experiments, the only class of graphs with proven performance guarantee of reductions rules was the class of planar graphs. However it was conjectured in that similar reduction rules can be proved to be efficient for more general graph classes like graphs of bounded genus. In this paper we (i) prove that the same rules, applied to any graph G of genus g, reduce the k-dominating set problem to a kernel of size O(k+g), i.e. linear kernel. This resolves a basic open question on the potential of kernel reduction for graph domination. (ii) Using such a kernel we improve the best so far algorithm for k-dominating set on graphs of genus ≤ g from \(2^{O(g\sqrt{k}+g^{2})}n^{O(1)}\) to \(2^{O(\sqrt{gk}+g)}+n^{O(1)}\). (iii) Applying tools from the topological graph theory, we improve drastically the best so far combinatorial bound to the branchwidth of a graph in terms of its minimum dominating set and its genus. Our new bound provides further exponential speed-up of our algorithm for the k-dominating set and we prove that the same speed-up applies for a wide category of parameterized graph problems such as k-vertex cover, k-edge dominating set, k-vertex feedback set, k-clique transversal number and several variants of the k-dominating set problem. A consequence of our results is that the non-parameterized versions of all these problems can be solved in subexponential time when their inputs have sublinear genus.
Part of this research has been initiated during the Dagstuhl Seminar no 01311 on Parameterized Complexity. The first author is supported by Norges forskningsråd project 160778/V30. The second author is supported by the EU within the 6th Framework Program under contract 001907 (DELIS) and by the Spanish CICYT project TIC-2002-04498-C05-03 (TRACER).
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
Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 461–493 (2002)
Alber, J., Fellows, M.R., Niedermeier, R.: Efficient data reduction for dominating set: A linear problem kernel for the planar case. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 150–159. Springer, Heidelberg (2002); To appear in the Journal of the ACM
Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI 2001), San Francisco, CA, pp. 7–15. Morgan Kaufmann Publishers, San Francisco (2001)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixedparameter algorithms for the (k, r)-center in planar graphs and map graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 829–844. Springer, Heidelberg (2003)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 823–832 (2004) (to appear)
Demaine, E.D., Hajiaghayi, M.: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2004) (to appear)
Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms on K3,3-minor-free or K5-minor-free graphs. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 262–273. Springer, Heidelberg (2002)
Djidjev, H.N., Venkatesan, S.M.: Planarization of graphs embedded on surfaces. In: Nagl, M. (ed.) WG 1995. LNCS, vol. 1017, pp. 62–72. Springer, Heidelberg (1995)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Ellis, J., Fan, H., Fellows, M.: The dominating set problem is fixed parameter tractable for graphs of bounded genus. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 180–189. Springer, Heidelberg (2002)
Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branchwidth and exponential speed-up. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 168–177 (2003)
Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs and fixed parameter algorithms, Technical Report 240, Department of Informatics, University of Bergen, Norway (2003); Extended abstract A Simple and Fast Approach for Solving Problems on Planar Graphs to appear in the proceedings of STACS 2004 (2004)
Kanj, I., Perković, L.: Improved parameterized algorithms for planar dominating set. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 399–410. Springer, Heidelberg (2002)
Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint set on plane and planar graphs. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 282–296. Springer, Heidelberg (2002)
Mohar, B., Thomassen, C.: Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)
Robertson, N., Seymour, P.D.: Graph minors. VII. Disjoint paths on a surface. J. Combin. Theory Ser. B 45, 212–254 (1988)
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to treedecomposition. Journal of Combinatorial Theory Series B 52, 153–190 (1991)
Robertson, N., Seymour, P.D.: Graph minors. XI. Circuits on a surface. J. Combin. Theory Ser. B 60, 72–106 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fomin, F.V., Thilikos, D.M. (2004). Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_50
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive