2026-08-06T10:28:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10970 2024-03-06T10:46:56Z ddc:004 open_access

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness Dörfler, Julian Roth, Marc Schmitt, Johannes Wellnitz, Philip counting complexity edge-transitive graphs graph homomorphisms induced subgraphs parameterized complexity We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for the complexity analysis of #IndSub(Phi), inspired by the "topological approach to evasiveness" of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a wide range of properties Phi. In this work, we refine this technique for graph properties that are non-trivial on edge-transitive graphs with a prime power number of edges. In particular, we fully classify the case of monotone bipartite graph properties: It is shown that, given any graph property Phi that is closed under the removal of vertices and edges, and that is non-trivial for bipartite graphs, the problem #IndSub(Phi) is #W[1]-hard and cannot be solved in time f(k)* n^{o(k)} for any computable function f, unless the Exponential Time Hypothesis fails. This holds true even if the input graph is restricted to be bipartite and counting is done modulo a fixed prime. A similar result is shown for properties that are closed under the removal of edges only. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian Dörfler and Marc Roth and Johannes Schmitt and Philip Wellnitz 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.26 urn:nbn:de:0030-drops-109703 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.26 eng https://creativecommons.org/licenses/by/3.0/legalcode