Math @ Duke

Publications [#348688] of Benjamin Rossman
Papers Published
 Kopparty, S; Rossman, B, The homomorphism domination exponent,
European Journal of Combinatorics, vol. 32 no. 7
(October, 2011),
pp. 10971114 [doi]
(last updated on 2022/05/21)
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 seriesparallel. © 2011 Elsevier Ltd.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

