Speakers
Description
Harry Vinall-Smeeth and Christoph Berkholz
Abstract: The task of computing homomorphisms between two finite relational
structures A and B is a well-studied question with
numerous applications. Since the set Hom(A,B) of all
homomorphisms may be very large having a method of representing it in
a succinct way, especially one which enables us to perform efficient
enumeration and counting, could be extremely useful.
One simple yet powerful way of doing so is to decompose
Hom(A,B) using union and Cartesian product.
Such data structures, called d-representations, have been introduced by
Olteanu and Zavodny in the context of
database theory. Their results also imply that if the treewidth of the left-hand
side structure A is bounded, then a d-representation of
polynomial size can be found in polynomial time. We show that for
structures of bounded arity this is optimal: if the treewidth is
unbounded then there are instances where the size of any
d-representation is superpolynomial. Along the way we develop tools
for proving lower bounds on the size of d-representations, in
particular we define a notion of reduction suitable for this context
and prove an almost tight lower bound on the size of d-representations
of all k-cliques in a graph.