Parameterized Counting and Cayley Graph Expanders
DOI10.1137/22m1479804MaRDI QIDQ6158357
Alina Vdovina, Norbert Peyerimhoff, Jakob Stix, Marc Roth, Philip Wellnitz, Johannes Schmitt
Publication date: 31 May 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
graph homomorphismscounting complexitysubgraphsCaley graph expandersfine-grained and parameterized complexity
Graph theory (including graph drawing) in computer science (68R10) Geometric group theory (20F65) Structure of modular groups and generalizations; arithmetic groups (11F06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quaternion and other division algebras: arithmetic, zeta functions (11R52) Combinatorial aspects of commutative algebra (05E40) Parameterized complexity, tractability and kernelization (68Q27) Expander graphs (05C48)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Structural tractability of counting of solutions to conjunctive queries
- Fundamentals of parameterized complexity
- The complexity of computing the permanent
- Cayley graph expanders and groups of finite width.
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. XX: Wagner's conjecture
- The complexity of counting homomorphisms seen from the other side
- Cayley digraphs of prime-power order are hamiltonian
- Counting induced subgraphs: a topological approach to \#W[1-hardness]
- Strong computational lower bounds via parameterized complexity
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Graph minors. V. Excluding a planar graph
- Ramanujan graphs
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Quickly excluding a planar graph
- Bicycle dimension and special points of the Tutte polynomial
- The parameterised complexity of counting even and odd induced subgraphs
- Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
- Parameterized complexity of finding subgraphs with hereditary properties.
- The parameterised complexity of counting connected subgraphs and graph motifs
- Narrow sieves for parameterized paths and packings
- Parameterized counting of trees, forests and matroid bases
- Parametrized complexity theory.
- On tree width, bramble size, and expansion
- Tight lower bounds for certain parameterized NP-hard problems
- Some Hard Families of Parameterized Counting Problems
- Deciding first-order properties of locally tree-decomposable structures
- PP is as Hard as the Polynomial-Time Hierarchy
- Deterministic Truncation of Linear Matroids
- Expander graphs and their applications
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- The Complexity of Enumeration and Reliability Problems
- An Algorithm for Subgraph Isomorphism
- Color-coding
- The Parameterized Complexity of the k -Biclique Problem
- The Parameterized Complexity of Counting Problems
- On the computational complexity of the Jones and Tutte polynomials
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Homomorphisms are a good basis for counting small subgraphs
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Counting Answers to Existential Questions
- The Complexity of Computing the Sign of the Tutte Polynomial
- Approximately counting and sampling small witnesses using a colourful decision oracle
- When is the evaluation of conjunctive queries tractable?
- Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
- Extensor-coding
- Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Paths, Trees, and Flowers
- Simply transitive quaternionic lattices of rank 2 overq(t) and a non-classical fake quadric
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- Parameterized Algorithms
- An Efficient Algorithm for Graph Isomorphism
- The complexity of theorem-proving procedures
- Transactions on Computational Systems Biology III
- On the complexity of \(k\)-SAT
- Parameterized (Modular) Counting and Cayley Graph Expanders
This page was built for publication: Parameterized Counting and Cayley Graph Expanders
