Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern

Abstract

The kTree problem is a special case of Subgraph Isomorphism where the pattern graph is a tree, that is, the input is an $n$-node graph $G$ and a $k$-node tree $T$, and the goal is to determine whether $G$ has a subgraph isomorphic to $T$. We provide evidence that this problem cannot be computed significantly faster than $2^k\text{poly}(n)$, which matches the fastest algorithm known for this problem by Koutis and Williams [ICALP 2009 and TALG 2016]. Specifically, we show that if kTree can be solved in time $(2-\epsilon {)}^k\text{poly}(n)$ for some constant $\epsilon >0$, then Set Cover with $n^{\prime }$ elements and $m^{\prime }$ sets can be solved in time $(2-\delta {)}^{n^{\prime }}\text{poly}(m^{\prime })$ for a constant $\delta (\epsilon )>0$, which would refute the Set Cover Conjecture by Cygan et al. [CCC 2012 and TALG 2016]. Our techniques yield a new algorithm for the p-Partial Cover problem, a parameterized version of Set Cover that requires covering at least $p$ elements (rather than all elements). Its running time is $(2+\epsilon {)}^p(m^{\prime }{)}^{O(1/\epsilon )}$ for any fixed $\epsilon >0$, which improves the previous $2.597^p\text{poly}(m^{\prime })$-time algorithm by Zehavi [ESA 2015]. Our running time is nearly optimal, as a $(2-{\epsilon }^{\prime }{)}^p\text{poly}(m^{\prime })$-time algorithm would refute the Set Cover Conjecture.

A merged work containing the results in this paper is available at arXiv:1711.08041

References in corpus (1)

• On Problems as Hard as CNFSAT