2026-08-04T07:43:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13549 2024-03-06T10:52:17Z ddc:004 open_access

The Strongish Planted Clique Hypothesis and Its Consequences Manurangsi, Pasin Rubinstein, Aviad Schramm, Tselil Planted Clique Densest k-Subgraph Hardness of Approximation We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time n^Ω(log n) (so that the state-of-the-art running time of n^O(log n) is optimal up to a constant in the exponent). We provide two sets of applications of the new hypothesis. First, we show that SPCH implies (nearly) tight inapproximability results for the following well-studied problems in terms of the parameter k: Densest k-Subgraph, Smallest k-Edge Subgraph, Densest k-Subhypergraph, Steiner k-Forest, and Directed Steiner Network with k terminal pairs. For example, we show, under SPCH, that no polynomial time algorithm achieves o(k)-approximation for Densest k-Subgraph. This inapproximability ratio improves upon the previous best k^o(1) factor from (Chalermsook et al., FOCS 2017). Furthermore, our lower bounds hold even against fixed-parameter tractable algorithms with parameter k. Our second application focuses on the complexity of graph pattern detection. For both induced and non-induced graph pattern detection, we prove hardness results under SPCH, improving the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under the Exponential Time Hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pasin Manurangsi and Aviad Rubinstein and Tselil Schramm 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.10 urn:nbn:de:0030-drops-135491 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.10 eng https://creativecommons.org/licenses/by/3.0/legalcode