AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
A dichotomy for real weighted Holant problems
Holant problems for 3-regular graphs with complex edge functions
A computational proof of complexity of some restricted counting problems
Representative families: a unified tradeoff-based approach
General factors of graphs
Matching theory
General antifactors of graphs
Optimal general matchings
Block interpolation: a framework for tight exponential-time counting complexity
Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday
Parameterized complexity of conflict-free matchings and paths
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
From Holant to #CSP and Back: Dichotomy for Holant c Problems
Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
Path coupling using stopping times and counting independent sets and colorings in hypergraphs
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Representative Families of Product Families
On the Complexity of Holant Problems
Representative Sets and Irrelevant Vertices
Paths, Trees, and Flowers
An exact characterization of tractable demand patterns for maximum disjoint path problems
Mathematical Foundations of Computer Science 2003
Parameterized Algorithms
The factorization of graphs. II
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
A Colored Path Problem and Its Applications
On the complexity of $k$-SAT

This page was built for publication: AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)