Abstract
Based on a series of known and new examples, we propose the generalized setting of “distance from triviality” measurement as a reasonable and prospective way of determining useful structural problem parameters in analyzing computationally hard problems. The underlying idea is to consider tractable special cases of generally hard problems and to introduce parameters that measure the distance from these special cases. In this paper we present several case studies of distance from triviality parameterizations (concerning Clique, Power Dominating Set, Set Cover, and Longest Common Subsequence) that exhibit the versatility of this approach to develop important new views for computational complexity analysis.
Supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group PIAF (fixed-parameter algorithms), NI 369/4.
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(4), 461–493 (2002)
Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: Refined search tree technique for Dominating Set on planar graphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 111–122. Springer, Heidelberg (2001)
Bodlaender, H.L.: Classes of graphs with bounded treewidth. Technical Report RUU-CS-86-22, Dept. of Computer Sci., Utrecht University (1986)
Bodlaender, H.L.: Treewidth: Algorithmic techniques and results. In: Privara, I., Ružička, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19–36. Springer, Heidelberg (1997)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of the longest common subsequence problem. Theoretical Computer Science 147, 31–54 (1995)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58, 171–176 (1996)
Cai, L.: Parameterized complexity of Vertex Colouring. Discrete Applied Mathematics 127(1), 415–429 (2003)
Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further observations and further improvements. J. Algorithms 41, 280–301 (2001)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs. In: Proc. 15th SODA, pp. 830–839. SIAM, Philadelphia (2004)
Downey, R.G.: Parameterized complexity for the skeptic. In: Proc. 18th IEEE Annual Conference on Computational Complexity, pp. 147–169 (2003)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999); 4 The latter being of particular interest when attacking W[1]-hard problems
Ellis, J., Fan, H., Fellows, M.R.: 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)
Fellows, M.R.: Blow-ups, win/win’s, and crown rules: Some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 1–12. Springer, Heidelberg (2003)
Fellows, M.R.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 505–520. Springer, Heidelberg (2003)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. In: CIAC 2003. LNCS, vol. 2653, pp. 108–119. Springer, Heidelberg (2003); To appear in Theory of Computing Systems.
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004)
Guo, J., Niedermeier, R.: Exact algorithms and applications for Tree-like Weighted Set Cover (June 2004) (manuscript)
Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discrete Math. 15(4), 519–529 (2002)
Hoffmann, M., Okamoto, Y.: The traveling salesman problem with few inner points. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 268–277. Springer, Heidelberg (2004)
Juedes, D., Chor, B., Fellows, M.R.: Linear kernels in linear time, or How to save k colors in O(n2) steps. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257–269. Springer, Heidelberg (2004) (to appear)
Niedermeier, R.: Ubiquitous parameterization—invitation to fixed-parameter algorithms. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 84–103. Springer, Heidelberg (2004) (to appear)
Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for Weighted Vertex Cover. J. Algorithms 47(2), 63–77 (2003)
Nishimura, N., Ragde, P., Thilikos, D.M.: Fast fixed-parameter tractable algorithms for nontrivial generalizations of Vertex Cover. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 75–86. Springer, Heidelberg (2001); To appear in Discrete Applied Mathematics
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425–440 (1991)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet Shortest Common Supersequence and Longest Common Subsequence problems. J. Comput. Syst. Sci. 67(4), 757–771 (2003)
Robertson, N., Seymour, P.D.: Graph minors. II: Algorithmic aspects of treewidth. J. Algorithms 7, 309–322 (1986)
Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425–440 (1986)
Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 548–558. Springer, Heidelberg (2003)
Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566–579 (1984)
Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol. 709, pp. 610–621. Springer, Heidelberg (1993)
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
Guo, J., Hüffner, F., Niedermeier, R. (2004). A Structural View on Parameterizing Problems: Distance from Triviality. In: Downey, R., Fellows, M., Dehne, F. (eds) Parameterized and Exact Computation. IWPEC 2004. Lecture Notes in Computer Science, vol 3162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28639-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-28639-4_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23071-7
Online ISBN: 978-3-540-28639-4
eBook Packages: Springer Book Archive