14:00
15:00

Title: Algorithmic Aspects of the Comparison of Phylogenetic Network Homomorphisms in graphs with forbidden structures
Abstract: For a fixed graph H, the H-coloring problem takes as an instance a graph G and asks whether there exists a homomorphism from G to H, i.e., a mapping f: V(G) -> V(H) such that if uv is an edge of G, then f(u)f(v) is an edge of H. Graph homomorphisms are a well-known generalization of graph colorings, one of the most popular and elegant objects in graph theory. Indeed, for any k>0, the notions of k-coloring and K_k-coloring (of G) coincide.

The H-coloring problem is polynomial-time solvable when H is bipartite or has a loop, and NP-complete otherwise. In general, the existence of algorithms solving NP-complete cases of H-coloring significantly faster than brute-force is unlikely under standard complexity assumptions. However, it is still possible to find algorithms working in time polynomial, or at least subexponential, in the size of the instance, if we put additional assumptions on the class of input instances. In this talk, I will show what can be achieved in the classes of F-free graphs, i.e., graphs defined by forbidding a fixed graph F as an induced subgraph. In particular, we examine to which extent the variety of tools developed to work on coloring and independent set problems in these graphs can be applied.

178