Campus Event Calendar
Event Entry
What and Who
Constraint satisfaction, tree duality and adjoint functors
Jan Foniok
ETH Zürich
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 24 September 2010
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
I like to think of constraint satisfaction as of the existence question of homomorphisms of relational structures (which is equivalent). A particular (but powerful) case are digraph homomorphisms: a homomorphism from a digraph G to a digraph H is a mapping from V(G) to V(H) that maps arcs of G to arcs of H (and non-arcs to anything). For input G and H it is, of course, NO-complete to decide whether a homomorphism from G to H exists. A
popular setting is to fix H and ask about the complexity of deciding the existence of a homomorphism from input G to the fixed H (= CSP(H)). For some H, CSP(H) is polynomial; among them are H with so-called tree duality. I will explain what tree duality is, show that it is preserved by taking the arc graph (as well as other right adjoint functors) and discuss some applications. Joint work with Claude Tardif.
Contact
Anna Huber
--email hidden
passcode not visible
logged in users only
Anna Huber, 09/03/2010 15:58 -- Created document.