Skip to main content
SpringerLink
Log in

k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2–3), 235–239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89–92, 1985), 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 (chordless) cycle of length greater than k, k≥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 polynomial-time algorithm that, given a graph G and k≥3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each 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 Δ has treewidth at most (k−1)(Δ−1)+2, improving the O(Δ(Δ−1)k−3) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(1–3), 45–61, 1997. Moreover, any graph admitting such a tree-decomposition has small hyperbolicity).

As an application, for any n-vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klogΔ+logn) bits and achieving an additive stretch of O(klogΔ). As far as we know, this is the first routing scheme with O(klogΔ+logn)-routing tables and small additive stretch for k-chordal graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, pp. 188–197. ACM, New York (2006)

    Chapter  Google Scholar 

  2. Abraham, I., Malkhi, D.: Name independent routing for growth bounded networks. In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’05, pp. 49–55. ACM, New York (2005)

    Google Scholar 

  3. Abraham, I., Gavoille, C., Malkhi, D.: Compact routing for graphs excluding a fixed minor. In: Distributed Computing. Lecture Notes in Computer Science, vol. 3724, pp. 442–456. Springer, Berlin (2005)

    Chapter  Google Scholar 

  4. Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: 26th IEEE International Conference on Distributed Computing Systems, 2006. ICDCS 2006, p. 75 (2006)

    Google Scholar 

  5. Abraham, I., Gavoille, C., Malkhi, D.: On space-stretch trade-offs: lower bounds. In: Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’06, pp. 207–216. ACM, New York (2006)

    Google Scholar 

  6. Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. ACM Trans. Algorithms 4(3), 37–13712 (2008)

    Article  MathSciNet  Google Scholar 

  7. Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Appl. Math. 8(1), 1–12 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  8. Aksoy, A.G., Jin, S.: The apple doesn’t fall far from the (metric) tree: the equivalence of definitions (2013). arXiv:1306.6092

  9. Andreae, T.: On a pursuit game played on graphs for which a minor is excluded. J. Comb. Theory, Ser. B 41(1), 37–47 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  10. Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discrete Methods 8(2), 277–284 (1987). http://epubs.siam.org/doi/pdf/10.1137/0608024

    Article  MATH  MathSciNet  Google Scholar 

  11. Bandelt, H., Chepoi, V.: 1-hyperbolic graphs. SIAM J. Discrete Math. 16(2), 323–334 (2003). http://epubs.siam.org/doi/pdf/10.1137/S0895480100380902

    Article  MATH  MathSciNet  Google Scholar 

  12. Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  13. Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1–2), 1–45 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  14. Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358–402 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  15. Bodlaender, H.L., Möhring, R.: The pathwidth and treewidth of cographs. SIAM J. Discrete Math. 6(2), 181–188 (1993). http://epubs.siam.org/doi/pdf/10.1137/0406014

    Article  MATH  MathSciNet  Google Scholar 

  16. Bodlaender, H.L., Thilikos, D.M.: Treewidth for graphs with small chordality. Discrete Appl. Math. 79(1–3), 45–61 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  17. Bonato, A., Nowakovski, R.: The Game of Cops and Robber on Graphs. American Math. Soc., Providence (2011)

    Book  Google Scholar 

  18. Cai, L., Chan, S.M., Chan, S.O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Proceedings 2nd International Workshop on Parameterized and Exact Computation, IWPEC 2006, pp. 239–250. Springer, Berlin (2006)

    Google Scholar 

  19. Chalopin, J., Chepoi, V., Nisse, N., Vaxès, Y.: Cop and robber games when the robber can hide and ride. SIAM J. Discrete Math. 25(1), 333–359 (2011). http://epubs.siam.org/doi/pdf/10.1137/100784035

    Article  MATH  MathSciNet  Google Scholar 

  20. Chen, Y., Flum, J.: On parameterized path and chordless path problems. In: Twenty-Second Annual IEEE Conference on Computational Complexity, 2007, CCC ’07, pp. 250–263 (2007)

    Google Scholar 

  21. Chen, W., Sommer, C., Teng, S.-H., Wang, Y.: Compact routing in power-law graphs. In: Distributed Computing. Lecture Notes in Computer Science, vol. 5805, pp. 379–391. Springer, Berlin (2009)

    Chapter  Google Scholar 

  22. Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vaxès, Y.: Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. In: Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, SCG ’08, pp. 59–68. ACM, New York (2008)

    Chapter  Google Scholar 

  23. Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vaxès, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for hyperbolic graphs. Algorithmica 62(3–4), 713–732 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  24. Clarke, N.E., Nowakowski, R.J.: Tandem-win graphs. Discrete Math. 299(1–3), 56–64 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  25. Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109(1–2), 49–82 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  26. de Montgolfier, F., Soto, M., Viennot, L.: Treewidth and hyperbolicity of the Internet. In: 10th IEEE International Symposium on Network Computing and Applications (NCA), pp. 25–32 (2011)

    Google Scholar 

  27. Dourisboure, Y.: Compact routing schemes for generalised chordal graphs. J. Graph Algorithms Appl. 9(2), 277–297 (2005)

    Article  MathSciNet  Google Scholar 

  28. Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Math. 307(16), 2008–2029 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  29. Fraigniaud, P., Gavoille, C.: Routing in trees. In: Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2076, pp. 757–772. Springer, Berlin (2001)

    Chapter  Google Scholar 

  30. Frankl, P.: Cops and robbers in graphs with large Girth and Cayley graphs. Discrete Appl. Math. 17(3), 301–305 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  31. Gromov, M.: Hyperbolic groups. Essays Group Theory 8, 75–263 (1987)

    MathSciNet  Google Scholar 

  32. Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973)

    Article  Google Scholar 

  33. Kloks, T., Kratsch, D.: Treewidth of chordal bipartite graphs. J. Algorithms 19(2), 266–281 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  34. Kobayashi, Y., Kawarabayashi, K.-i.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’09, pp. 1146–1155 (2009)

    Chapter  Google Scholar 

  35. Konjevod, G., Richa, A.W., Xia, D.: Optimal-stretch name-independent compact routing in doubling metrics. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, pp. 198–207. ACM, New York (2006)

    Chapter  Google Scholar 

  36. Kosowski, A., Li, B., Nisse, N., Suchan, K.: k-chordal graphs: from cops and robber to compact routing via treewidth. In: Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 7392, pp. 610–622. Springer, Berlin (2012)

    Chapter  Google Scholar 

  37. Krioukov, D., Papadopoulos, F., Boguñá, M., Vahdat, A.: Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces. ACM SIGMETRICS Perform. Eval. Rev. 37(2), 15–17 (2009)

    Article  Google Scholar 

  38. Lokshtanov, D.: On the complexity of computing treelength. Discrete Appl. Math. 158(7), 820–827 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  39. Lu, L., Peng, X.: On Meyniel’s conjecture of the cop number. J. Graph Theory 71(2), 192–205 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  40. Nisse, N., Rapaport, I., Suchan, K.: Distributed computing of efficient routing schemes in generalized chordal graphs. Theor. Comput. Sci. 444, 17–27 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  41. Nowakowski, R., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discrete Math. 43(2–3), 235–239 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  42. Opsahl, T., Panzarasa, P.: Clustering in weighted networks. Soc. Netw. 31(2), 155–163 (2009)

    Article  Google Scholar 

  43. Quilliot, A.: A short note about pursuit games played on a graph with a given genus. J. Comb. Theory, Ser. B 38(1), 89–92 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  44. Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B 36(1), 49–64 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  45. Schröder, B.S.W.: The copnumber of a graph is bounded by \(\lfloor\frac{3}{2} \mathit{genus}({G})\rfloor+ 3\). In: Categorical Perspectives. Trends in Mathematics, pp. 243–263. Birkhäuser, Boston (2001)

    Chapter  Google Scholar 

  46. Scott, A., Sudakov, B.: A bound for the cops and robbers problem. SIAM J. Discrete Math. 25(3), 1438–1442 (2011). http://epubs.siam.org/doi/pdf/10.1137/100812963

    Article  MATH  MathSciNet  Google Scholar 

  47. Sundaram, R., Singh, K., Rangan, C.: Treewidth of circular-arc graphs. SIAM J. Discrete Math. 7(4), 647–655 (1994). http://epubs.siam.org/doi/pdf/10.1137/S0895480191193789

    Article  MATH  MathSciNet  Google Scholar 

  48. Uehara, R.: Tractable and intractable problems on generalized chordal graphs. Technical Report COMP98-83, IEICE (1999)

  49. Watts, D.J., Strogatz, S.: Collective dynamics of ’small-world’ networks. Nature 393(6684), 440–442 (1998)

    Article  Google Scholar 

  50. Wu, Y., Zhang, C.: Hyperbolicity and chordality of a graph. Electron. J. Comb. 18(1) (2011)

Download references

Author information

Author notes

  1. B. Li

    Present address: Institute of Applied Mathematics, AAMS, CAS, Beijing, China

Authors and Affiliations

  1. CEPAGE, INRIA, LaBRI, Talence, France

    A. Kosowski

  2. Coati Project, INRIA, I3S(CNRS/UNS), Sophia Antipolis, France

    B. Li & N. Nisse

  3. FIC, Universidad Adolfo Ibáñez, Santiago, Chile

    K. Suchan

  4. WMS, AGH, University of Science and Technology, Krakow, Poland

    K. Suchan

Authors
  1. A. Kosowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. Nisse
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. K. Suchan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to B. Li.

Additional information

Partially supported by programs Fondap and Basal-CMM, Anillo ACT88 and Fondecyt 11090390 (K.S.), FP7 STREP EULER (N.N.), AGAPE, ECOS-SUD, EA. AlDyNet, ANR DISPLEXITY, NCN under contract DEC-2011/02/A/ST6/00201 (A.K.).

This work has been announced at the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012); the extended abstract appeared in the corresponding proceedings [36].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kosowski, A., Li, B., Nisse, N. et al. k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth. Algorithmica 72, 758–777 (2015). https://doi.org/10.1007/s00453-014-9871-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-014-9871-y

Keywords

Search

Navigation