The Strongish Planted Clique Hypothesis and Its Consequences
The Strongish Planted Clique Hypothesis and Its Consequences
复制标题
强势派系假说及其后果
DOI：
10.4230/lipics.itcs.2021.10
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
T. Schramm
中科院分区：
文献类型：
--
作者：
Pasin Manurangsi;A. Rubinstein;T. Schramm
我们制定了一个新的硬度假设，强种植集团假设（SPCH），它假设任何种植集团的算法必须在时间$n^{\Omega（\log{n}）}$内运行（因此最先进的运行时间$n^{O（\log n）}$是最佳的，直到指数为常数）。
我们提供了两套新假设的应用。首先，我们表明，SPCH意味着（近）紧不可逼近的结果，以下研究问题的参数$k$：Denmark $k$-子图，最小的$k$-边子图，Denmark $k$-子超图，Steiner $k$-森林，和有向Steiner网络与$k$终端对。例如，我们表明，在SPCH下，没有多项式时间算法实现$o（k）$-近似Denise $k$-子图。该不可近似性比改进了来自（Chalermsook等人，FOCS 2017）。此外，我们的下界甚至对固定参数易处理的算法与参数$k$。
我们的第二个应用程序集中在复杂的图形模式检测。对于诱导和非诱导图形模式检测，我们证明了SPCH下的硬度结果，这改善了由（Dalirrooyfard等人，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^{\Omega(\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.
DOI：
10.1145/3055399.3055412
发表时间：
2016-11
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Pasin Manurangsi
通讯作者：
Pasin Manurangsi
DOI：
10.4230/lipics.approx-random.2016.6
发表时间：
2016-05
期刊：
ArXiv
影响因子：
--
作者：
E. Chlamtác;M. Dinitz;C. Konrad;G. Kortsarz;George Rabanca
通讯作者：
E. Chlamtác;M. Dinitz;C. Konrad;G. Kortsarz;George Rabanca