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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221115T163000
DTEND;TZID=Asia/Seoul:20221115T173000
DTSTAMP:20260419T224722
CREATED:20221011T041240Z
LAST-MODIFIED:20240705T171137Z
UID:6283-1668529800-1668533400@dimag.ibs.re.kr
SUMMARY:Sebastian Wiederrecht\, Excluding single-crossing matching minors in bipartite graphs
DESCRIPTION:By a seminal result of Valiant\, computing the permanent of (0\, 1)-matrices is\, in general\, #P-hard. In 1913 Pólya asked for which (0\, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975\, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3\,3}$ as a matching minor. This was turned into a polynomial time algorithm by McCuaig\, Robertson\, Seymour\, and Thomas in 1999. However\, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3\,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0\, 1)-matrices can be computed efficiently. \nIn this paper we unify the two results above into a single\, more general result in the style of the celebrated structure theorem for single-crossing minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3\,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover\, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude $K_{5\,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem\, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth. \nThis is joint work with Archontia Giannopoulou and Dimitrios Thilikos.
URL:https://dimag.ibs.re.kr/event/2022-11-15/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR