DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.79

Being Even Slightly Shallow Makes Life Hard

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

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{muzi_et_al:LIPIcs.MFCS.2017.79,
  author =	{Muzi, Irene and O'Brien, Michael P. and Reidl, Felix and Sullivan, Blair D.},
  title =	{{Being Even Slightly Shallow Makes Life Hard}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{79:1--79:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.79},
  URN =		{urn:nbn:de:0030-drops-81257},
  doi =		{10.4230/LIPIcs.MFCS.2017.79},
  annote =	{Keywords: Topological minors, NP Completeness, Treewidth, ETH, FPT algorithms}
}

Search Results

Documents authored by O'Brien, Michael P.

Being Even Slightly Shallow Makes Life Hard

Abstract

Cite as

Thanks for your feedback!

Could not send message