Roman Bacik, Sanjeev Mahajan

The graph homomorphism problem is a canonical $NP$-complete problem.

It generalizes various other well-studied problems such as graph

coloring and finding cliques. To get a better insight into a

combinatorial problem, one often studies relaxations of the problem.

We define fractional homomorphisms and pseudo-homomorphisms ...
more >>>

Asaf Shapira, Noga Alon

Property-testers are fast randomized algorithms for distinguishing

between graphs (and other combinatorial structures) satisfying a

certain property, from those that are far from satisfying it. In

many cases one can design property-testers whose running time is in

fact {\em independent} of the size of the input. In this paper we

more >>>