Abstract
Many algorithms for FPT graph problems are search tree algorithms with sophisticated local branching rules. But it has also been noticed that using the global structure of input graphs complements the the search tree paradigm. Here we prove some new results based on the global structure of bounded-degree graphs after branching away the high-degree vertices. Some techniques and structural results are generic and should find more applications. First, we decompose a graph by “separating” branchings into cheaper or smaller components wich are then processed separately. Using this idea we accelerate the O *(1.3803k) time algorithm for counting the vertex covers of size k (Mölle, Richter, and Rossmanith, 2006) to O *(1.3740k). Next we characterize the graphs where no edge is in three conflict triples, i.e., triples of vertices with exactly two edges. This theorem may find interest in graph theory, and it yields an O *(1.47k) time algorithm for Cluster Deletion, improving upon the previous O *(1.53k) (Gramm, Guo, Hüffner, Niedermeier, 2004). Cluster Deletion is the problem of deleting k edges to destroy all conflict triples and get a disjoint union of cliques. For graphs where every edge is in O(1) conflict triples we show a nice dichotomy: The graph or its complement has degree O(1). This opens the possibility for future improvements via the above decomposition technique.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Böcker, S., Briesemeister, S., Bui, Q.B.A., Truß, A.: Going Weighted: Parameterized Algorithms for Cluster Editing. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 1–12. Springer, Heidelberg (2008)
Damaschke, P.: Fixed-Parameter Enumerability of Cluster Editing and Related Problems. Theory Comp. Systems (to appear)
Damaschke, P., Mololov, L.: The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting. J. Discr. Alg. (to appear)
Dehne, F., Langston, M.A., Luo, X., Pitre, S., Shaw, P., Zhang, Y.: The Cluster Editing Problem: Implementations and Experiments. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 13–24. Springer, Heidelberg (2006)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On Two Techniques of Combining Branching and Treewidth. Algorithmica (to appear)
Fomin, F.V., Hoie, K.: Pathwidth of Cubic Graphs and Exact Algorithms. Info. Proc. Letters 97, 191–196 (2006)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems. Algorithmica 39, 321–347 (2004)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation. Theory Comp. Systems 38, 373–392 (2005)
Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-Parameter Algorithms for Cluster Vertex Deletion. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 711–722. Springer, Heidelberg (2008)
Kneis, J., Langer, A., Rossmanith, P.: Improved Upper Bounds for Partial Vertex Cover. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 240–251. Springer, Heidelberg (2008)
Mölle, D., Richter, S., Rossmanith, P.: Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 265–273. Springer, Heidelberg (2006)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Math. and its Appl. Oxford Univ. Press, Oxford (2006)
Shamir, R., Sharan, R., Tsur, D.: Cluster Graph Modification Problems. Discr. Appl. Math. 144, 173–182 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damaschke, P. (2009). Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms. In: Chen, J., Fomin, F.V. (eds) Parameterized and Exact Computation. IWPEC 2009. Lecture Notes in Computer Science, vol 5917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11269-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-11269-0_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11268-3
Online ISBN: 978-3-642-11269-0
eBook Packages: Computer ScienceComputer Science (R0)