Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejc.2011.03.009 | Eur. J. Comb. |
Keywords | Field | DocType |
graphs f,linear program,isolating class,graph t.,homomorphism domination problem,homomorphism domination exponent,maximum real number,lower bound,important open question,computational property,series parallel,relational database,upper and lower bounds | Discrete mathematics,Combinatorics,Exponent,Upper and lower bounds,Chordal graph,Decidability,Linear programming,Homomorphism,Real number,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
32 | 7 | 0195-6698 |
Citations | PageRank | References |
2 | 0.40 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Benjamin Rossman | 2 | 298 | 20.00 |