2026-08-11T00:06:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8125 2024-03-06T10:40:59Z ddc:004 open_access

Being Even Slightly Shallow Makes Life Hard Muzi, Irene O'Brien, Michael P. Reidl, Felix Sullivan, Blair D. Topological minors NP Completeness Treewidth ETH FPT algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irene Muzi and Michael P. O'Brien and Felix Reidl and Blair D. Sullivan 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.79 urn:nbn:de:0030-drops-81257 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.79 eng https://creativecommons.org/licenses/by/3.0/legalcode