On the maximum cardinality search lower bound for treewidth

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 vv in an MCS-ordering is the number of neighbours of vv that are before vv in the ordering. The visited degree of an MCS-ordering ψψ of GG is the maximum visited degree over all vertices vv in ψψ. The maximum visited degree over all MCS-orderings of graph GG is called its maximum visited degree  . Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345–353] showed that the treewidth of a graph GG is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn)O(logn) for planar graphs, and give examples of planar graphs GG with maximum visited degree kk with O(k!)O(k!) vertices, for all k∈Nk∈N. Given a graph GG, it is NP-complete to determine if its maximum visited degree is at least kk, for any fixed k⩾7k⩾7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NPP=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.