Abstract
The Maximum Cardinality Search algorithm visits the vertices of a graph in an order such that at any point, a vertex is visited that has the largest number of visited neighbours. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The MCSLB of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. Lucena [10] showed that the treewidth of a graph G is at least the MCSLB of any MCS-ordering of G.
In this paper, we analyse the maximum MCSLB over all possible MCS-orderings of given graphs G. We give upper and lower bounds for this number for planar graphs. Given a graph G, it is NP-complete to determine if G has an MCS-ordering with MCSLB at least k, for any fixed k≥ 7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.
We also propose and experimentally analysed some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the maximum MCSLB that an MCS-ordering can obtain which appear to give results close to optimal on several graphs from real life applications.
This research has been partially supported by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4, and partially by the Netherlands Organisation for Scientific Research NWO (project Treewidth and Combinatorial Optimisation).
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
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. In: Proceedings 6th Workshop on Algorithm Engineering and Experiments ALENEX 2004, pp. 70–78 (2004)
Bodlaender, H.L., Koster, A.M.C.A., van den Eijkhof, F., van der Gaag, L.C.: Pre-processing for triangulation of probabilistic networks. In: Breese, J., Koller, D. (eds.) Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp. 32–39. Morgan Kaufmann, San Francisco (2001)
Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. Technical report UU-CS-2004-034, Institute of Information and Computing Sciences, Utrecht University (2004); To appear in proceedings ESA 2004
Clautiaux, F., Carlier, J., Moukrim, A., Négre, S.: New lower and upper bounds for graph treewidth. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol. 2647, pp. 70–80. Springer, Heidelberg (2003)
Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. To appear in proceedings UAI 2004, Uncertainty in Artificial Intelligence (2004)
Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. In: Broersma, H., Faigle, U., Hurink, J., Pickl, S. (eds.) Electronic Notes in Discrete Mathematics, vol. 8. Elsevier Science Publishers, Amsterdam (2001)
Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks 40, 170–180 (2002)
Lauritzen, S.J., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. The Journal of the Royal Statistical Society Series B (Methodological) 50, 157–224 (1988)
Lucena, B.: A new lower bound for tree-width using maximum cardinality search. SIAM J. Disc. Math. 16, 345–353 (2003)
Ramachandramurthi, S.: The structure and number of obstructions to treewidth. SIAM J. Disc. Math. 10, 146–157 (1997)
Röhrig, H.: Tree decomposition: A feasibility study. Master’s thesis, Max-Planck- Institut für Informatik, Saarbrücken, Germany (1998)
Szekeres, G., Wilf, H.S.: An inequality for the chromatic number of a graph. J. Comb. Theory 4, 1–3 (1968)
Tarjan, R.E., Yannakakis, M.: Simple linear time algorithms to test chordiality of graphs, test acyclicity of graphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566–579 (1984)
van den Eijkhof, F., Bodlaender, H.L.: Safe reduction rules for weighted treewidth. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 176–185. Springer, Heidelberg (2002)
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
Bodlaender, H.L., Koster, A.M.C.A. (2004). On the Maximum Cardinality Search Lower Bound for Treewidth. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30559-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-30559-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24132-4
Online ISBN: 978-3-540-30559-0
eBook Packages: Computer ScienceComputer Science (R0)