NDLI: Slightly Superexponential Parameterized Problems

Please wait, while we are loading the content...

Slightly Superexponential Parameterized Problems

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Lokshtanov, Daniel Marx, Dániel Saurabh, Saket
Copyright Year	2018
Abstract	A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot n^{O(1)}$ such that $f$ is as slow growing a function of the parameter $k$ as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where $f(k)$ is single-exponential, that is, $c^k$ for some constant $c$, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the $f(k)$ appearing in the best-known running time is worse than single-exponential and it remained slightly superexponential even after serious attempts to bring it down. A natural question to ask is whether the $f(k)$ appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where $f(k)$ is $k^{O(k)}=2^{O(k\log k)}$ in the best-known running time, and for a number of such problems we show that the dependence on $k$ in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings $s_1$, $\dots$, $s_t$ over an alphabet $\Sigma$ of length $L$ each, and an integer $d$, the question is whether there exists a string $s$ over $\Sigma$ of length $L$, such that its hamming distance from each of the strings $s_i$, $1\leq i \leq t$, is at most $d$. The pattern matching problem Closest String is known to be solvable in times $2^{O(d\log d)}\cdot n^{O(1)}$ and $2^{O(d\log \|\Sigma\|)}\cdot n^{O(1)}$. We show that there are no $2^{o(d\log d)}\cdot n^{O(1)}$ or $2^{o(d\log \|\Sigma\|)}\cdot n^{O(1)}$ time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph $G$ has a metric embedding into the integers with distortion at most $d$ can be solved in time $2^{O(d\log d)}\cdot n^{O(1)}$. We show that there is no $2^{o(d\log d)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time $2^{O(w\log w)}\cdot n^{O(1)}$ on graphs of treewidth at most $w$. We show that there is no $2^{o(w\log w)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time $2^{O(w\log w)}\cdot n^{O(1)}$ on graphs of treewidth at most $w$. We show that there is no $2^{o(w\log w)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future.
Sponsorship	H2020 European Research Council
Starting Page	675
Ending Page	702
Page Count	28
File Format	PDF
ISSN	00975397
DOI	10.1137/16M1104834
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3 (Special Section on the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015))
Volume Number	47
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2018-05-22
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems closest string exponential time hypothesis parameterized complexity lower bound treewidth distortion
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Isomorphism Between Subexponential and Parameterized Complexity Theory

Closest Substring Problems with Small Distances

Slightly Superexponential Parameterized Problems

Hitting minors on bounded treewidth graphs. III. Lower bounds

Lower Bounds on the Complexity of MSO_1 Model-Checking

Metric Dimension Parameterized by Treewidth

Lower Bounds on the Complexity of MSO_1 Model-Checking

On the parameterized complexity of approximate counting

Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width

Slightly Superexponential Parameterized Problems

Similar Documents

An Isomorphism Between Subexponential and Parameterized Complexity Theory

Closest Substring Problems with Small Distances

Slightly Superexponential Parameterized Problems

Hitting minors on bounded treewidth graphs. III. Lower bounds

Lower Bounds on the Complexity of MSO_1 Model-Checking

Metric Dimension Parameterized by Treewidth

Lower Bounds on the Complexity of MSO_1 Model-Checking

On the parameterized complexity of approximate counting

Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width

Slightly Superexponential Parameterized Problems