Professor Norbert Peyerimhoff norbert.peyerimhoff@durham.ac.uk
Professor
Parameterized Counting and Cayley Graph Expanders
Peyerimhoff, Norbert; Roth, Marc; Schmitt, Johannes; Stix, Jakob; Vdovina, Alina; Wellnitz, Philip
Authors
Marc Roth
Johannes Schmitt
Jakob Stix
Alina Vdovina
Philip Wellnitz
Abstract
Given a graph property \Phi , we consider the problem \# EdgeSub(\Phi ), where the input is a pair of a graph G and a positive integer k, and the task is to compute the number of k-edge subgraphs in G that satisfy \Phi . Specifically, we study the parameterized complexity of \#EdgeSub(\Phi ) with respect to both approximate and exact counting, as well as its decision version EdgeSub(\Phi ). Among others, our main result fully resolves the case of minor-closed properties \Phi : the decision problem EdgeSub(\Phi ) always admits a fixed-parameter tractable algorithm, and the counting problem \#EdgeSub(\Phi ) always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property \Phi which, if satisfied, yields fixed-parameter tractability and otherwise \#\sansW [1]-hardness. Additionally, our hardness results come with an almost tight conditional lower bound under the exponential time hypothesis. Our main technical result concerns the exact counting problem: Building upon the breakthrough result of Curticapean, Dell, and Marx (Symposium on Theory of Computing 2017), we express the number of subgraphs satisfying \Phi as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of p-groups, which might be of independent interest. The properties of those expanders allow us to analyze the coefficients in the aforementioned linear combinations over the field \BbbF p which gives us significantly more control over the cancelation behavior of the coefficients.
Citation
Peyerimhoff, N., Roth, M., Schmitt, J., Stix, J., Vdovina, A., & Wellnitz, P. (2023). Parameterized Counting and Cayley Graph Expanders. SIAM Journal on Discrete Mathematics, 37(2), 405-486. https://doi.org/10.1137/22m1479804
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 13, 2022 |
Online Publication Date | Apr 16, 2023 |
Publication Date | 2023-06 |
Deposit Date | Jun 7, 2023 |
Publicly Available Date | Jun 7, 2023 |
Journal | SIAM Journal on Discrete Mathematics |
Print ISSN | 0895-4801 |
Electronic ISSN | 1095-7146 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 37 |
Issue | 2 |
Pages | 405-486 |
DOI | https://doi.org/10.1137/22m1479804 |
Public URL | https://durham-repository.worktribe.com/output/1173068 |
Files
Published Journal Article
(4.2 Mb)
PDF
Copyright Statement
© 2023 Society for Industrial and Applied Mathematics.
You might also like
Eigenvalue estimates for the magnetic Hodge Laplacian on differential forms
(2023)
Journal Article
Bakry–Émery Curvature Sharpness and Curvature Flow in Finite Weighted Graphs. Implementation
(2023)
Journal Article
Going round in circles: Geometry in the early years
(2023)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search