On the maximum cardinality search lower bound for treewidth.

*(English)*Zbl 1119.05101Summary: The maximum cardinality search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS 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 visited degree of an MCS-ordering \(\psi\) of \(G\) is the maximum visited degree over all vertices \(v\) in \(\psi\). The maximum visited degree over all MCS-orderings of graph \(G\) is called its maximum visited degree. B. Lucena [SIAM J. Discrete Math. 16, 345–353 (2003; Zbl 1041.68071)] showed that the treewidth of a graph \(G\) is at least its maximum visited degree.

We show that the maximum visited degree is of size \(O(\log n)\) for planar graphs, and give examples of planar graphs \(G\) with maximum visited degree \(k\) with \(O(k!)\) vertices, for all \(k \in \mathbb N\). Given a graph \(G\), it is NP-complete to determine if its maximum visited degree is at least \(k\), for any fixed \(k\geqslant 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.

In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.

We show that the maximum visited degree is of size \(O(\log n)\) for planar graphs, and give examples of planar graphs \(G\) with maximum visited degree \(k\) with \(O(k!)\) vertices, for all \(k \in \mathbb N\). Given a graph \(G\), it is NP-complete to determine if its maximum visited degree is at least \(k\), for any fixed \(k\geqslant 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.

In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.

##### MSC:

05C85 | Graph algorithms (graph-theoretic aspects) |

68Q25 | Analysis of algorithms and problem complexity |

68R10 | Graph theory (including graph drawing) in computer science |

##### Software:

Treewidthlib
PDF
BibTeX
XML
Cite

\textit{H. L. Bodlaender} and \textit{A. M. C. A. Koster}, Discrete Appl. Math. 155, No. 11, 1348--1372 (2007; Zbl 1119.05101)

Full Text:
DOI

**OpenURL**

##### References:

[1] | E. Amir, Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 2001, pp. 7-15. |

[2] | Bachoore, E.H.; Bodlaender, H.L., New upper bound heuristics for treewidth, (), 217-227 · Zbl 1121.68355 |

[3] | Becker, A.; Geiger, D., A sufficiently fast algorithm for finding close to optimal clique trees, Artificial intelligence, 125, 3-17, (2001) · Zbl 0972.68152 |

[4] | Bodlaender, H.L.; Grigoriev, A.; Koster, A.M.C.A., Treewidth lower bounds with brambles, (), 391-402 · Zbl 1162.68490 |

[5] | Bodlaender, H.L.; Koster, A.M.C.A., Safe separators for treewidth, Discrete math., 306, 337-350, (2006) · Zbl 1084.05065 |

[6] | Bodlaender, H.L.; Koster, A.M.C.A.; Eijkhof, F.v.d., Pre-processing rules for triangulation of probabilistic networks, Comput. intelligence, 21, 3, 286-305, (2005) |

[7] | H.L. Bodlaender, A.M.C.A. Koster, T. Wolle, Contraction and treewidth lower bounds, Journal on Graph Algorithms and Applications, 10 (2006) 5-49. · Zbl 1161.68644 |

[8] | Clautiaux, F.; Carlier, J.; Moukrim, A.; Négre, S., New lower and upper bounds for graph treewidth, (), 70-80 · Zbl 1023.68645 |

[9] | Clautiaux, F.; Moukrim, A.; Négre, S.; Carlier, J., Heuristic and meta-heuristic methods for computing graph treewidth, RAIRO oper. res., 38, 13-26, (2004) · Zbl 1092.90065 |

[10] | Eijkhof, F.v.d.; Bodlaender, H.L., Safe reduction rules for weighted treewidth, (), 176-185 · Zbl 1022.68604 |

[11] | F.v.d. Eijkhof, H.L. Bodlaender, A.M.C.A. Koster, Safe reduction rules for weighted treewidth, Algorithmica 47 (2007) 139-158. · Zbl 1108.68091 |

[12] | V. Gogate, R. Dechter, A complete anytime algorithm for treewidth, in: Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence UAI-04, Arlington, VA, USA, AUAI Press, 2004, pp. 201-208. |

[13] | Koster, A.M.C.A.; Bodlaender, H.L.; van Hoesel, S.P.M., Treewidth: computational experiments, (), 54-57 · Zbl 1409.05176 |

[14] | Koster, A.M.C.A.; van Hoesel, S.P.M.; Kolen, A.W.J., Solving partial constraint satisfaction problems with tree decomposition, Networks, 40, 3, 170-180, (2002) · Zbl 1027.90072 |

[15] | Koster, A.M.C.A.; Wolle, T.; Bodlaender, H.L., Degree-based treewidth lower bounds, (), 101-112 · Zbl 1121.68346 |

[16] | Lauritzen, S.J.; Spiegelhalter, D.J., Local computations with probabilities on graphical structures and their application to expert systems, J. R. statist. soc. ser. B, 157-224, (1988) · Zbl 0684.68106 |

[17] | B. Lucena, Dynamic programming, tree-width, and computation on graphical models, Ph.D. Thesis, Brown University, Providence, RI, USA, 2002. |

[18] | Lucena, B., A new lower bound for tree-width using maximum cardinality search, SIAM J. discrete math., 16, 345-353, (2003) · Zbl 1041.68071 |

[19] | Robertson, N.; Seymour, P.D., Graph minors. II. algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017 |

[20] | Sunil Chandran, L.; Subramanian, C.R., A spectral lower bound for the treewidth of a graph and its consequences, Inform. process. lett., 87, 195-200, (2003) · Zbl 1161.68647 |

[21] | Sunil Chandran, L.; Subramanian, C.R., Girth and treewidth, J. combin. theory ser. B, 93, 23-32, (2005) · Zbl 1064.05084 |

[22] | Tarjan, R.E.; Yannakakis, M., Simple linear time algorithms to test chordiality of graphs, and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062 |

[23] | Treewidthlib, \(\langle\)http://www.cs.uu.nl/people/hansb/treewidthlib⟩, 2004. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.