Lower bounds for the graph homomorphism problem

-CSP problem. In this paper, we prove several lower bound for HOM under the Exponential Time Hypothesis (ETH) assumption. The main result is a lower bound

2^{O m e g a l e f t (f r a c n l o g h l o g l o g h i g h t)}

. This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound

2^{m a t h c a l O (n l o g h)}

is almost asymptotically tight. We also investigate what properties of graphs

G

and

H

make it difficult to solve HOM

(G, H)

. An easy observation is that an

m a t h c a l O (h^{n})

upper bound can be improved to

m a t h c a l O (h^{o p e r a t o r n a m e v c (G)})

where

o p e r a t o r n a m e v c (G)

is the minimum size of a vertex cover of

G

. The second lower bound

h^{O m e g a (o p e r a t o r n a m e v c (G))}

shows that the upper bound is asymptotically tight. As to the properties of the "right-hand side" graph

H

, it is known that HOM

(G, H)

can be solved in time

(f (D e l t a (H)))^{n}

and

(f (o p e r a t o r n a m e t w (H)))^{n}

where

D e l t a (H)

is the maximum degree of

H

and

o p e r a t o r n a m e t w (H)

is the treewidth of

H

. This gives single-exponential algorithms for graphs of bounded maximum degree or bounded treewidth. Since the chromatic number

c h i (H)

does not exceed

o p e r a t o r n a m e t w (H)

and

D e l t a (H) + 1

, it is natural to ask whether similar upper bounds with respect to

c h i (H)

can be obtained. We provide a negative answer to this question by establishing a lower bound

(f (c h i (H)))^{n}

for any function

f

. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Lower bounds for the graph homomorphism problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448809)