***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Paweł Rzążewski (Warsaw U.)
Tuesday 5th February, 3:00 in Fine Hall 224.
Title: Finding list homomorphisms from bounded-treewidth graphs to
reflexive graphs
In the ``list homomorphism'' problem, the input consists of two graphs G and H,
together with a list L(v) of vertices of H for every vertex v in V(G).
The task is to find a homomorphism phi:V(G)->V(H) respecting the lists,
that is, we have that phi(v) is in L(v) for every v in V(H), and if u and v
are adjacent in G, then phi(u) and phi(v) are adjacent in H. If H is a fixed
graph, then the problem is denoted LHOM(H).
We consider the ``reflexive'' version of the problem, where we assume that
every vertex in H has a self-loop. It is known that reflexive LHOM(H) is
polynomial-time solvable if H is an interval graph and it is NP-complete
otherwise [Feder and Hell, JCTB 1998].
We explore the complexity of the problem parameterized by the treewidth
tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is
given in the input, then the problem can be solved in time
|V(H)|^{tw(G)}n^{O(1)} by naive dynamic programming. Our main result
completely reveals when and by exactly how much this naive algorithm can be
improved. We introduce a simple combinatorial invariant i*(H), which is
based on the existence of decompositions and incomparable sets, and show that
this number should appear as the base of the exponent in the best possible
running time. Specifically, we prove for every fixed graph H that
--- If a tree decomposition of width tw(G) is given in the input,
then the problem can be solved in time i*(H)^{tw(G)}n^{O(1)}.
--- Assuming the Strong Exponential-Time Hypothesis (SETH), the problem
cannot be solved in time (i*(H)-c)^{tw(G)}n^{O(1)} for any c>0.
Thus by matching upper and lower bounds, our result exactly
characterizes for every fixed H the complexity of reflexive LHOM(H)
parameterized by treewidth.
These results are joint work with Laszlo Ergi and Daniel Marx.
----------------------------------
This week (Thursday): no speaker
Next week: Ron Aharoni
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)