68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Refine
Document Type
- ZIB-Report (3)
Language
- English (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- lower bounds (3) (remove)
Institute
- ZIB Allgemein (3)
In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs.
The Maximum Cardinality Search 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 neighbors becomes visited. 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 neighbors 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 {\em maximum visited degree}. Lucena (2003) 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 \Bbb{N}$. Given a graph $G$, it is NP-complete to determine if its maximum visited degree is at least $k$, for any fixed $k\geq 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 analyses 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 value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.
Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed $k$, it is polynomial time decidable if a given graph $G$ has contraction degeneracy at least $k$. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search (Lucena, 2003). Finally, heuristics for the treewidth are proposed and! evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al (2003).