Parameterised and fine-grained subgraph counting, modulo 2
From MaRDI portal
Publication:6130316
DOI10.1007/s00453-023-01178-0arXiv2301.01696MaRDI QIDQ6130316
Leslie Ann Goldberg, Marc Roth
Publication date: 2 April 2024
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2301.01696
Cites Work
- Fundamentals of parameterized complexity
- The complexity of counting homomorphisms seen from the other side
- The treewidth of line graphs
- Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness]
- Strong computational lower bounds via parameterized complexity
- Faster algorithms for counting subgraphs in sparse graphs
- Parametrized complexity theory.
- On tree width, bramble size, and expansion
- Tight lower bounds for certain parameterized NP-hard problems
- PP is as Hard as the Polynomial-Time Hierarchy
- The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Color-coding
- The Parameterized Complexity of Counting Problems
- Homomorphisms are a good basis for counting small subgraphs
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Finding Four-Node Subgraphs in Triangle Time
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Parameterized Algorithms
- Counting Subgraphs in Degenerate Graphs
- On the complexity of \(k\)-SAT
- Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
- Parameterized (Modular) Counting and Cayley Graph Expanders
- Parameterized Counting and Cayley Graph Expanders
This page was built for publication: Parameterised and fine-grained subgraph counting, modulo 2
