License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.9
URN: urn:nbn:de:0030-drops-69426
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6942/
Go to the corresponding LIPIcs Volume Portal

Brand, Cornelius ; Dell, Holger ; Roth, Marc

Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP

pdf-format:
LIPIcs-IPEC-2016-9.pdf (0.5 MB)

Abstract

Jaeger, Vertigan, and Welsh (1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén (2010) and Husfeldt and Taslaman (2010), in combination with the results of Curticapean (2015), extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line y=1, which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given n-vertex graph cannot be determined in time exp(o(n)) unless #ETH fails.

Another dichotomy theorem we strengthen is the one of Creignou and Hermann (1996) for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases cannot be solved in time exp(o(n)) unless #ETH fails. The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails.

In order to prove our results, we use the block interpolation idea by Curticapean (2015) and transfer it to systems of linear equations that might not directly correspond to interpolation.

BibTeX - Entry

@InProceedings{brand_et_al:LIPIcs:2017:6942,
  author =	{Cornelius Brand and Holger Dell and Marc Roth},
  title =	{{Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6942},
  URN =		{urn:nbn:de:0030-drops-69426},
  doi =		{10.4230/LIPIcs.IPEC.2016.9},
  annote =	{Keywords: computational complexity, counting problems, Tutte polynomial, exponential time hypothesis, forests, independent sets}
}

Keywords: computational complexity, counting problems, Tutte polynomial, exponential time hypothesis, forests, independent sets
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI