BEGIN:VCALENDAR
VERSION:2.0
PRODID:-// - ECPv5.3.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://aarms.math.ca
X-WR-CALDESC:Events for 
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20231122T153000
DTEND;TZID=UTC:20231122T163000
DTSTAMP:20260415T045029
CREATED:20231118T113007Z
LAST-MODIFIED:20231118T113007Z
UID:7454-1700667000-1700670600@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar
DESCRIPTION:Speaker:  Santiago Guzman-Pro\, TU Dresden\nTitle:          Forbidden Tournaments and the Orientation (Completion) Problem\n\nAbstract:   For a fixed finite set of  oriented graphs F\,  the F-free  orientation problem asks\nwhether a given finite undirected graph G has an F-free orientation\, i.e.\, whether the edges\nof  G  can be  oriented so that the  resulting  oriented  graph does not contain  any oriented\ngraph from F as an oriented (induced) subgraph. It was first noted by Bang-Jensen\, Huang\,\nand Prisner that when F is a set of oriented paths on 3 vertices\, this problem easily reduces\nto 2-SAT\, and thus is solvable in polynomial-time. This was later extended to sets of oriented\ngraphs on 3 vertices (G.P.\ and Hernández-Cruz 2017). Towards a complete understanding\nof the complexity of the F-free orientation problem\,  we consider the case when  F is a set of\nfinite  tournaments.     We prove that  for every  such  F\,  this problem is in P or NP-complete.Specifically\, we show that either the F-free orientation problem can be reduced (in polynomial-\ntime) to a system of Boolean linear equations\, or the F-free orientation problem is NP-complete.\nThis  dichotomy result is  accompanied  by a  classification  statement  which\, given a set of\ntournaments  F\,   allows  us  to decide  whether  the  F-free  orientation  problem  is in  P  or\nNP-complete. We reduce this classification task to a complete complexity classification of the\norientation completion problem for F\, which is the variant of the problem above where the input\nis a partially oriented graph instead of an undirected graph\, introduced by Bang-Jensen\, Huang\,\nand Zhu (2017). Our proof uses results from the theory of constraint satisfaction\, and a result\nof Agarwal and Kompatscher (2018) about infinite permutation groups and transformation monoids.\n\nThis is joint work with Manuel Bodirsky.
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-6/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette%20Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
END:VCALENDAR