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.