BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210506T100000
DTEND;TZID=Asia/Seoul:20210506T110000
DTSTAMP:20260420T091913
CREATED:20210319T045807Z
LAST-MODIFIED:20240705T190027Z
UID:3813-1620295200-1620298800@dimag.ibs.re.kr
SUMMARY:Raul Lopes\, Adapting the Directed Grid Theorem into an FPT Algorithm
DESCRIPTION:The Grid Theorem of Robertson and Seymour [JCTB\, 1986] is one of the most important tools in the field of structural graph theory\, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB\, 2001] \, and proved by Kawarabayashi and Kreutzer [STOC\, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor and stated that their proof can be turned into an XP algorithm\, with parameter k\, that either constructs a decomposition of the appropriate width\, or finds the claimed large cylindrical grid as a butterfly minor. \nIn this talk\, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k that is contained in the set of vertices of a path hitting all elements of B. As tools to prove these results\, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|. \nJoint work with Victor Campos\, Ana Karolinna Maia\, and Ignasi Sau.
URL:https://dimag.ibs.re.kr/event/2021-05-06/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210512T170000
DTEND;TZID=Asia/Seoul:20210512T180000
DTSTAMP:20260420T091913
CREATED:20210319T045925Z
LAST-MODIFIED:20240705T190026Z
UID:3816-1620838800-1620842400@dimag.ibs.re.kr
SUMMARY:Johannes Carmesin\, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings
DESCRIPTION:Given a graph\, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion\, this problem would be NP-hard. Instead of minimum genus\, here we use local planarity — and provide a polynomial algorithm. \nOur embedding method is based on Whitney’s trick to use matroids to construct embeddings in the plane. Consequently we obtain a characterisation of the graphs admitting locally planar embeddings in surfaces in terms of a certain matroid being co-graphic.
URL:https://dimag.ibs.re.kr/event/2021-05-12/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210521T170000
DTEND;TZID=Asia/Seoul:20210521T180000
DTSTAMP:20260420T091913
CREATED:20210319T050153Z
LAST-MODIFIED:20240705T190024Z
UID:3818-1621616400-1621620000@dimag.ibs.re.kr
SUMMARY:Benjamin Bumpus\, Directed branch-width: A directed analogue of tree-width
DESCRIPTION:Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example\, consider classes of bounded tree- or clique-width. Since the 1990s\, many directed analogues of tree-width have been proposed. However\, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’. \nIn this talk\, I will introduce a new tree-width analogue for digraphs called directed branch-width which allows us to define digraph classes for which many problems (including directed HamiltonPath and MaxCut)  become linear-time solvable. Furthermore\, via the definition of directed branch-width\, I will obtain a generalisation to digraphs of Gurski and Wanke’s characterization of graph classes of bounded tree-width in terms of their line graphs. \nThis is joint work with Kitty Meeks and William Pettersson.
URL:https://dimag.ibs.re.kr/event/2021-05-21/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210526T170000
DTEND;TZID=Asia/Seoul:20210526T180000
DTSTAMP:20260420T091913
CREATED:20210424T122241Z
LAST-MODIFIED:20240707T081338Z
UID:3986-1622048400-1622052000@dimag.ibs.re.kr
SUMMARY:Dimitrios M. Thilikos\, Bounding Obstructions sets: the cases of apices of minor closed classes
DESCRIPTION:Given a minor-closed graph class ${\cal G}$\, the (minor) obstruction of ${\cal G}$ is the set of all minor-minimal graphs not in ${\cal G}$. Given a non-negative integer $k$\, we define the $k$-apex of ${\cal A}$ as the class containing every graph $G$ with a set $S$ of vertices whose removal from $G$ gives a graph on ${\cal G}$. We prove that every obstruction of the $k$-apex of ${\cal G}$ has size bounded by some 4-fold exponential function of $p(k)$ where p is a polynomial function whose degree depends on the size of the minor-obstructions of ${\cal G}$. This bound drops to a 2-fold exponential one when ${\cal G}$ excludes some apex graph as a minor (i.e.\, a graph in the $1$-apex of planar graphs). \nJoint work with Ignasi Sau and Giannos Stamoulis.
URL:https://dimag.ibs.re.kr/event/2021-05-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR