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 >>>

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>