License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.79
URN: urn:nbn:de:0030-drops-81257
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8125/
Go to the corresponding LIPIcs Volume Portal

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

Being Even Slightly Shallow Makes Life Hard

pdf-format:
LIPIcs-MFCS-2017-79.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{muzi_et_al:LIPIcs:2017:8125,
  author =	{Irene Muzi and Michael P. O'Brien and Felix Reidl and Blair D. Sullivan},
  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 =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8125},
  URN =		{urn:nbn:de:0030-drops-81257},
  doi =		{10.4230/LIPIcs.MFCS.2017.79},
  annote =	{Keywords: Topological minors, NP Completeness, Treewidth, ETH, FPT algorithms}
}

Keywords: Topological minors, NP Completeness, Treewidth, ETH, FPT algorithms
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI