enter search term and/or author name
The complexity of the comparator circuit value problem
Stephen A. Cook, Yuval Filmus, Dai Tri Man Lê
Article No.: 15
In 1990, Subramanian  defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL ⊆ CC ⊆ P, and proved that in addition to CCV several other...
FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders
Michael R. Fellows, Bart M. P. Jansen
Article No.: 16
Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable obstruction sets and efficient order tests is not just one way of...
The complexity of counting homomorphisms to cactus graphs modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Article No.: 17
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally...