CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013

Complexity and Reductions
Chair: Alejandro Erickson (University of Victoria)
[PDF]

ANDREI BULATOV, Simon Fraser University
Counting CSPs and Datalog fixed points  [PDF] [SLIDES]

The problem of counting independent sets in bipartite graphs (num-BIS) is important in the study of the approximation complexity of counting CSPs. In their 2003 paper Dyer et al. proved that one of the problems interreducible (with respect to approximation preserving reductions) with num-BIS is the problem of counting fixed points of a linear Datalog program. We try to determine for which relational structures B there is a parsimonious reduction from num-CSP(B) to the problem of finding the number of fixed points.

ROSS CHURCHLEY, Simon Fraser University
Algorithms and obstructions for tree-transverse matchings  [PDF] [SLIDES]

A matching $M$ in a graph $G$ is called $T$-transverse if $G-M$ does not contain $T$ as a subgraph. Finding $T$-transverse matchings is generally NP-complete, even when $T$ is a (large-diameter) tree, but efficient algorithms are available for a few small cases. The $P_4$-transverse matching problem, for instance, has at least two good solutions: a reduction to 2-SAT and a reduction to the perfect matching problem. The second reduction extends to chair-transverse matchings, but seemingly not to cross-transverse matchings. This talk will compare these known algorithms for finding tree-transverse matchings and investigate their connection to the structure of minimal obstructions.

ALEJANDRO ERICKSON, University of Victoria
Domino tatami cover is NP-complete  [PDF] [SLIDES]

Domino coverings are a well studied area of classical enumerative combinatorics, yet locally restricted coverings have been scarcely considered. A covering with dominoes, of a rectilinear region, is called tatami if no four dominoes meet at any point.

I will present a straightforward and highly visual reduction from planar 3SAT to Domino Tatami Covering, and I will describe how we used SAT solvers to find the (hand-verifiable) gadgets required for the proof.

This is joint work with Dr. Frank Ruskey.

BUNDIT LAEKHANUKIT, McGill University
Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems  [PDF] [SLIDES]

We investigate the connection between the parameters of Two-Prover-One-Round Game (2P1R) and the hardness of approximating connectivity problems. Based on the recent development on 2P1R by Chan (STOC 2013), we improve hardness of connectivity problems that are in the form $k^\delta$, for some small constant $\delta > 0$, to hardness of the form $k^c$ for some explicit constant $c$, where $k$ is a connectivity parameter. Moreover, we prove hardness in terms of the number of demand pairs for the target problems. This improves upon the known hardness results of the rooted $k$-connectivity, vertex-connectivity survivable network design and vertex-connectivity $k$-route-cut problems.