Algorithms and Complexity Seminar

The Homomorphism Domination Exponent

Swastik Kopparty (MIT)

For fixed graphs F and G, we study the relationship between the number of homomorphisms from F to T and from G to T for an arbitrary graph T. We define the homomorphism domination exponent of F and G, denoted by hde(F,G), to be the largest constant c such that |Hom(F,T)| \geq |Hom(G,T)|^c for all T. The decidability of "hde(F,G) \geq 1" is an important open question in database theory (known as the containment problem for conjunctive queries with multiset semantics). We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of F and G where hde(F,G) can be computed exactly. In particular, we show that hde(F,G) is computable when F is chordal and G is series-parallel.

Our techniques are based on information theory and linear programming, and generalize the entropy variants of Shearer's lemma due to Radhakrishnan, Friedgut, Kahn and others.

Joint work with Ben Rossman (MIT).