# KLN+12c

### Summary

**Kosowski, A., Li, B., Nisse, N. and Suchan, K.** (2012) *k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.* In 14es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel). may, pages 83-86. ((URL)) (PDF)

### Abstract

{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of {$k$}-chordal graphs, i.e., graphs with no induced cycle of length greater than {$k$}, {$k\geq 3$}. We prove that {$k-1$} cops are always sufficient to capture a robber in {$k$}-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including {$k$}-chordal graphs. We present a quadratic algorithm that, given a graph {$G$} and {$k\geq 3$}, either returns an induced cycle larger than {$k$} in {$G$}, or computes a {\it tree-decomposition} of {$G$}, each {\it bag} of which contains a dominating path with at most {$k-1$} vertices. This allows us to prove that any {$k$}-chordal graph with maximum degree {$\Delta$} has treewidth at most {$(k-1)(\Delta-1)+2$}, improving the {$O(\Delta (\Delta-1)^{k-3})$} bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has hyperbolicity {$\leq\lfloor \frac{3}{2}k\rfloor$}. As an application, for any {$n$}-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size {$O(\log n)$} bits and achieving an additive stretch of {$O(k\log \Delta)$}. As far as we know, this is the first routing scheme with {$O(\log n)$}-routing tables and small additive stretch for {$k$}-chordal graphs. #KLN+12cBib

### Bibtex entry

`@INPROCEEDINGS { KLN+12c,`

AUTHOR = { Kosowski, A. and Li, B. and Nisse, N. and Suchan, K. },

TITLE = { k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth },

BOOKTITLE = { 14es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel) },

YEAR = { 2012 },

MONTH = { may },

PAGES = { 83-86 },

ABSTRACT = { {\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of {$k$}-chordal graphs, i.e., graphs with no induced cycle of length greater than {$k$}, {$k\geq 3$}. We prove that {$k-1$} cops are always sufficient to capture a robber in {$k$}-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including {$k$}-chordal graphs. We present a quadratic algorithm that, given a graph {$G$} and {$k\geq 3$}, either returns an induced cycle larger than {$k$} in {$G$}, or computes a {\it tree-decomposition} of {$G$}, each {\it bag} of which contains a dominating path with at most {$k-1$} vertices. This allows us to prove that any {$k$}-chordal graph with maximum degree {$\Delta$} has treewidth at most {$(k-1)(\Delta-1)+2$}, improving the {$O(\Delta (\Delta-1)^{k-3})$} bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has hyperbolicity {$\leq\lfloor \frac{3}{2}k\rfloor$}. As an application, for any {$n$}-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size {$O(\log n)$} bits and achieving an additive stretch of {$O(k\log \Delta)$}. As far as we know, this is the first routing scheme with {$O(\log n)$}-routing tables and small additive stretch for {$k$}-chordal graphs. },

URL = { http://hal.inria.fr/hal-00671861 },

PDF = { http://hal.archives-ouvertes.fr/docs/00/67/18/97/PDF/RR-7888.pdf },

}