Parameterized Counting and Cayley Graph Expanders
From MaRDI portal
Caley graph expanderscounting complexityfine-grained and parameterized complexitygraph homomorphismssubgraphs
Expander graphs (05C48) Combinatorial aspects of commutative algebra (05E40) Structure of modular groups and generalizations; arithmetic groups (11F06) Quaternion and other division algebras: arithmetic, zeta functions (11R52) Geometric group theory (20F65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
Cites work
- An Algorithm for Subgraph Isomorphism
- An Efficient Algorithm for Graph Isomorphism
- scientific article; zbMATH DE number 7052900
- Approximately counting and sampling small witnesses using a colourful decision oracle
- Bicycle dimension and special points of the Tutte polynomial
- Can you beat treewidth?
- Cayley digraphs of prime-power order are hamiltonian
- Cayley graph expanders and groups of finite width.
- Color-coding
- Counting Answers to Existential Questions
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- Counting matchings of size \(k\) is \#W[1]-hard
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Deciding first-order properties of locally tree-decomposable structures
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Expander families and Cayley graphs. A beginner's guide
- Expander graphs and their applications
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Extensor-coding
- Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fundamentals of parameterized complexity
- Graph minors. V. Excluding a planar graph
- Graph minors. XX: Wagner's conjecture
- Homomorphisms are a good basis for counting small subgraphs
- scientific article; zbMATH DE number 49189 (Why is no real title available?)
- scientific article; zbMATH DE number 139776 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- scientific article; zbMATH DE number 233957 (Why is no real title available?)
- Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
- Large networks and graph limits
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Narrow sieves for parameterized paths and packings
- On the complexity of k-SAT
- On the computational complexity of the Jones and Tutte polynomials
- On tree width, bramble size, and expansion
- Parameterized (Modular) Counting and Cayley Graph Expanders
- Parameterized algorithms
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized counting of trees, forests and matroid bases
- Parametrized complexity theory.
- Paths, Trees, and Flowers
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- PP is as Hard as the Polynomial-Time Hierarchy
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Quickly excluding a planar graph
- Ramanujan graphs
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Simply transitive quaternionic lattices of rank \(2\) over \(\mathbb{F}_q(t)\) and a non-classical fake quadric
- Some hard families of parameterized counting problems
- Strong computational lower bounds via parameterized complexity
- Structural tractability of counting of solutions to conjunctive queries
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The complexity of computing the permanent
- The complexity of computing the sign of the Tutte polynomial
- The complexity of counting homomorphisms seen from the other side
- The Complexity of Enumeration and Reliability Problems
- The complexity of theorem-proving procedures
- The parameterised complexity of counting connected subgraphs and graph motifs
- The parameterised complexity of counting even and odd induced subgraphs
- The Parameterized Complexity of Counting Problems
- The parameterized complexity of the k-biclique problem
- The theory of graphs. Translated from the 1958 French edition by Alison Doig.
- Tight lower bounds for certain parameterized NP-hard problems
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Transactions on Computational Systems Biology III
- Understanding the Complexity of Induced Subgraph Isomorphisms
- When is the evaluation of conjunctive queries tractable?
Cited in
(7)- Hypergraph expanders from Cayley graphs
- The shrinking-and-expanding method for the graph enumeration
- scientific article; zbMATH DE number 919838 (Why is no real title available?)
- Parameterised and fine-grained subgraph counting, modulo 2
- Counting subgraphs in somewhere dense graphs
- On the complexity of establishing hereditary graph properties via vertex splitting
- Parameterised holant problems
This page was built for publication: Parameterized Counting and Cayley Graph Expanders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158357)
