2026-08-05T23:31:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19759 2024-03-11T06:37:05Z ddc:004 open_access

Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs Liu, Ying Chen, Shiteng computational complexity planar Holant polynomial interpolation rETH sub-exponential #ETH #Matching #VC This article focuses on the sub-exponential time lower bounds for two canonical #P-hard problems: counting the vertex covers of a given graph (#VC) and counting the matchings of a given graph (#Matching), under the well-known counting exponential time hypothesis (#ETH). Interpolation is an essential method to build reductions in this article and in the literature. We use the idea of block interpolation to prove that both #VC and #Matching have no 2^{o(N)} time deterministic algorithm, even if the given graph with N vertices is a 3-regular graph. However, when it comes to proving the lower bounds for #VC and #Matching on planar graphs, both block interpolation and polynomial interpolation do not work. We prove that, for any integer N > 0, we can simulate N pairwise linearly independent unary functions by gadgets with only O(log N) size in the context of #VC and #Matching. Then we use log-size gadgets in the polynomial interpolation to prove that planar #VC and planar #Matching have no 2^{o(√{N/(log N)})} time deterministic algorithm. The lower bounds hold even if the given graph with N vertices is a 3-regular graph. Based on a stronger hypothesis, randomized exponential time hypothesis (rETH), we can avoid using interpolation. We prove that if rETH holds, both planar #VC and planar #Matching have no 2^{o(√N)} time randomized algorithm, even that the given graph with N vertices is a planar 3-regular graph. The 2^{Ω(√N)} time lower bounds are tight, since there exist 2^{O(√N)} time algorithms for planar #VC and planar #Matching. We also develop a fine-grained dichotomy for a class of counting problems, symmetric Holant*. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ying Liu and Shiteng Chen 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.49 urn:nbn:de:0030-drops-197593 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.49 eng https://creativecommons.org/licenses/by/4.0/legalcode