Document Open Access Logo

Fixed-parameter Tractable Distances to Sparse Graph Classes

Authors Jannis Bulian, Anuj Dawar

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.236.pdf
  • Filesize: 491 kB
  • 12 pages

Document Identifiers

Author Details

Jannis Bulian
Anuj Dawar

Cite As Get BibTex

Jannis Bulian and Anuj Dawar. Fixed-parameter Tractable Distances to Sparse Graph Classes. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 236-247, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.236

Abstract

We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to C is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT.  The second shows that determining the elimination distance of a graph G to a minor-closed class C is FPT.

Subject Classification

Keywords
  • parameterized complexity
  • fixed-parameter tractable
  • distance
  • graph theory
  • sparse graphs
  • graph minor
  • nowhere dense

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. I. Adler, M. Grohe, and S. Kreutzer. Computing excluded minors. In SODA'08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. SIAM, January 2008. Google Scholar
  2. J. Bulian and A. Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. In Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, pages 135-146, 2014. Google Scholar
  3. L. Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58:171-176, 1996. Google Scholar
  4. R. Diestel. Graph Theory. Springer, January 2000. Google Scholar
  5. R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, October 2012. Google Scholar
  6. J. Flum and M. Grohe. Fixed-Parameter Tractability, Definability, and Model-Checking. SIAM J. Comput., 31(1):113-145, 2001. Google Scholar
  7. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, May 2006. Google Scholar
  8. F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 470-479, 2012. Google Scholar
  9. J. Gajarský, P. Hlinený, J. Obdrzálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sanchez Villaamil, and S. Sikdar. Kernelization using structural parameters on sparse graph classes. In Algorithms - ESA 2013 - 21st Annual European Symposium, pages 529-540, 2013. Google Scholar
  10. P. A. Golovach. Editing to a Graph of Given Degrees. In Parameterized and Exact Computation, pages 196-207. Springer, September 2014. Google Scholar
  11. M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. In STOC'14: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, May 2014. Google Scholar
  12. J. Guo, F. Hüffner, and R. Niedermeier. A Structural View on Parameterizing Problems: Distance from Triviality. In Parameterized and Exact Computation, pages 162-173. Springer, 2004. Google Scholar
  13. W. Hodges. A Shorter Model Theory. Cambridge University Press, 1997. Google Scholar
  14. F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier. Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst., 47:196-217, 2010. Google Scholar
  15. D. Marx. Parameterized coloring problems on chordal graphs. Theor. Comput. Sci., 351:407-424, 2006. Google Scholar
  16. J. Nesetril and P. Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms. Springer, 2012. Google Scholar
  17. R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, February 2006. Google Scholar
  18. N. Robertson and P. D. Seymour. Graph minors. XX. wagner’s conjecture. J. Comb. Theory, Ser. B, 92:325-357, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact