论文标题
强大的种植集团假设及其后果
The Strongish Planted Clique Hypothesis and Its Consequences
论文作者
论文摘要
我们制定了一个新的硬度假设，即强烈的种植集团假设（SPCH），该假设（SPCH）假定，任何种植集团的算法都必须在时间$ n^{ω（\ log {n}）} $（因此，$ n^{o（log log n）$的最佳运行时间$ n^{ω（\ log {n}）} $是最佳的。 我们提供了新假设的两组应用。 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.例如，我们在SPCH下表明，没有多项式时间算法可以实现$ O（k）$ - 近似值$ k $ -subgraph。这种不Xibibibibibibibio的比率在先前的最佳$ k^{o（1）} $因子（Chalermsook等人，FOCS 2017）上提高。此外，我们的下限甚至与固定参数可处理算法有关，该算法和参数$ k $。 我们的第二个应用集中在图模式检测的复杂性上。对于诱导的和非诱导的图形模式检测，我们在SPCH下证明了硬度结果，这改善了（Dalirroyfard等，Stoc，2019年）在指数时间假设下获得的运行时间下限。
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, which improves the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under the Exponential Time Hypothesis.
