The homomorphism domination exponent

Swastik Kopparty, Benjamin Rossman

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)|≥|Hom(G,T)|c for every graph T. The problem of determining whether HDE(F,G)≥1 is known as the homomorphism domination problem, and its decidability is an important open question arising in the theory of relational databases. We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of graphs F and G for which HDE(F,G) is computable. In particular, we present a linear program computing HDE(F,G) in the special case, where F is chordal and G is series-parallel.

Original languageEnglish (US)
Pages (from-to)1097-1114
Number of pages18
JournalEuropean Journal of Combinatorics
Volume32
Issue number7
DOIs
StatePublished - Oct 1 2011

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Cite this