CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Algorithms and Complexity I

AMIR HEDAYATY, Simon Fraser University
On the complexity of approximate counting of CSPs  [PDF]

Approximate counting of solutions of Constraint Satisfaction Problems (\#CSP) has received much attention recently. Unlike exact counting, whose complexity is fully studied and proved to be either \#P-Complete or polytime, approximate complexity is much more diverse. We focus on \#BIS, the class in which the problem of counting independent sets in a bipartite graph is complete up to approximation preserving reductions. In this joint work with Andrei Bulatov, we present several easiness and hardness results.

KHALEGH MAMAKANI, University of Victoria, Canada
Generating All Simple Convexly-Drawable Polar-Symmetric 6-Venn Diagrams  [PDF]

An $n$-Venn diagram consists of $n$ curves that divide the plane into $2^n$ connected regions, one region for each possible intersection of the interiors of the curves. We show there are exactly 406 $6$-Venn diagrams that (a) have 6 curves, (b) are simple (at most two curves intersect at any point), (c) can be drawn with all curves convex, and (d) are invariant under ``polar flips", a type of inversion symmetry. Joint with Frank Ruskey.

JOHAN OPPEN, Molde University College
Connected sequences  [PDF]

We present a combinatorial problem where the idea is to build a picture or map piece by piece in such a way that it stays connected at all times during the building phase. Computational methods, both exact and approximate, to count the number of such connected sequences, are presented.

MAREK TESAR, Charles University, Prague
Locally injective homomorphism to the simple Weight graphs  [PDF]

A Weight graph is a connected (multi)graph with two vertices $u$ and $v$ of degree at least three and other vertices of degree two. A Weight graph is called simple if the degree of $u$ and $v$ is three. We show full computational complexity characterization of the problem of deciding the existence of a locally injective homomorphism from an input graph $G$ to any fixed simple Weight graph by identifying polynomial cases and NP-complete cases.

AARON WILLIAMS, Carleton University
New Constructions for Universal Cycles and de Bruijn Cycles  [PDF]

At the 2010 AMS/MAA meeting, Don Knuth described a construction for shorthand universal cycles of permutations that originated from CanaDAM 2007. Fixed-density de Bruijn cycles were constructed at CanaDAM 2009. We generalize these results: Given a multiset $M$ containing $f_i$ copies of $i$ for $1\le i\le n$, we construct shorthand universal cycles for the permutations of $M$. (Previous results use $f_i=1$, and $n=2$, respectively.) Collaborators: Alexander Holroyd, Frank Ruskey, Joe Sawada, Brett Stevens, Chi-Him Wong.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria