Document Open Access Logo

Being Even Slightly Shallow Makes Life Hard

Authors Irene Muzi, Michael P. O'Brien, Felix Reidl, Blair D. Sullivan

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.79.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Author Details

Irene Muzi
Michael P. O'Brien
Felix Reidl
Blair D. Sullivan

Cite As Get BibTex

Irene Muzi, Michael P. O'Brien, Felix Reidl, and Blair D. Sullivan. Being Even Slightly Shallow Makes Life Hard. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.79

Abstract

We study the computational complexity of identifying dense substructures, namely r/2-shallow topological minors and r-subdivisions. Of particular interest is the case r = 1, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms.
In the following, we provide a negative answer: Dense r/2-Shallow Topological Minor and Dense r-Subdivsion are already NP-hard for r = 1 in very sparse graphs. Further, they do not admit algorithms with running time 2^(o(tw^2)) n^O(1) when parameterized by the treewidth of the input graph for r > 2 unless ETH fails.

Subject Classification

Keywords
  • Topological minors
  • NP Completeness
  • Treewidth
  • ETH
  • FPT algorithms

Metrics

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

References

  1. S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. Google Scholar
  2. H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In International Colloquium on Automata, Languages, and Programming, pages 196-207. Springer, 2013. Google Scholar
  3. H. L. Bodlaender, T. Wolle, and A. Koster. Contraction and treewidth lower bounds. J. Graph Algorithms Appl., 10(1):5-49, 2006. Google Scholar
  4. J. Chen, X. Huang, I. A. Kanj, and G. Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 72(8):1346-1367, 2006. Google Scholar
  5. M. Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Lower bounds based on the exponential-time hypothesis. In Parameterized Algorithms, pages 467-521. Springer, 2015. Google Scholar
  6. M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, van J.M.M. Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In \FOCS52nd, pages 150-159. IEEE Computer Society, 2011. Google Scholar
  7. E. D. Demaine and M. Hajiaghayi. The bidimensionality theory and its algorithmic applications. The Computer Journal, 51(3):292-302, 2008. Google Scholar
  8. F. Dorn, F. V. Fomin, and D. M. Thilikos. Subexponential parameterized algorithms. Computer Science Review, 2(1):29-39, 2008. Google Scholar
  9. P. G. Drange, M. Dregi, F.V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, S. Saurabh, F. Sánchez Villaamil, S. Siebertz, and S. Sikdar. Kernelization and sparseness: the case of dominating set. In 33rd Symposium on Theoretical Aspects of Computer Science, 2016. Google Scholar
  10. Z. Dvořák. Asymptotical Structure of Combinatorial Objects. PhD thesis, Charles University, Faculty of Mathematics and Physics, 2007. Google Scholar
  11. Z. Dvořák, D. Král, and R. Thomas. Deciding first-order properties for sparse graphs. In \FOCS51st, pages 133-142. IEEE Computer Society, 2010. Google Scholar
  12. F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Linear kernels for (connected) dominating set on H-minor-free graphs. In \SODA23rd, pages 82-93. SIAM, 2012. Google Scholar
  13. J. Gajarský, P. Hliněný, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sánchez Villaamil, and S. Sikdar. Kernelization using structural parameters on sparse graph classes. To appear in Journal of Computer and System Sciences, 2016. Google Scholar
  14. G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1):30-55, 1989. Google Scholar
  15. A. V. Goldberg. Finding a maximum density subgraph. University of California Berkeley, CA, 1984. Google Scholar
  16. M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. In \STOC46th, pages 89-98, 2014. Google Scholar
  17. W. Mulzer and G. Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM (JACM), 55(2):11, 2008. Google Scholar
  18. J. Nešetřil and P. Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  19. M. Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: a logical approach. In International Symposium on Mathematical Foundations of Computer Science, pages 520-531. Springer, 2011. Google Scholar
  20. F. Reidl. Structural sparseness and complex networks. Dr., Aachen, Techn. Hochsch., Aachen, 2016. Aachen, Techn. Hochsch., Diss., 2015. URL: http://publications.rwth-aachen.de/record/565064.
  21. T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226. ACM, 1978. 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