BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200707T163000
DTEND;TZID=Asia/Seoul:20200707T173000
DTSTAMP:20260424T080950
CREATED:20200526T020628Z
LAST-MODIFIED:20240707T083806Z
UID:2481-1594139400-1594143000@dimag.ibs.re.kr
SUMMARY:Seog-Jin Kim (김석진)\, Online DP-coloring of graphs
DESCRIPTION:Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number\, $\chi_P(G)$\, (the minimum number of colors needed for an online coloring of $G$) and the DP-chromatic number\, $\chi_{DP}(G)$\, (the minimum number of colors needed for a DP-coloring of $G$) is at least the list chromatic number\, $\chi_\ell(G)$\, of $G$ and can be much larger. On the other hand\, each of them has a number of useful properties.\nWe introduce a common generalization\, online DP-coloring\, of online list coloring and DP-coloring and to study its properties. This is joint work with Alexandr Kostochka\, Xuer Li\, and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2020-07-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200714T163000
DTEND;TZID=Asia/Seoul:20200714T173000
DTSTAMP:20260424T080950
CREATED:20200708T123817Z
LAST-MODIFIED:20240707T083801Z
UID:2622-1594744200-1594747800@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Inverse Turán Problems
DESCRIPTION:For given graphs $G$ and $F$\, the Turán number $ex(G\,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a dual version of this problem wherein for a given number $k$\, one maximizes the number of edges in a host graph $G$ for which $ex(G\,H) < k$.  We resolve a problem of Briggs and Cox in the negative by showing that the inverse Turán number of $C_4$ is $\Theta(k^{3/2})$. More generally\, we determine the order of magnitude of the inverse Turán number of $K_{s\,t}$ for all $s$ and $t$.  Addressing another problem of Briggs and Cox\, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length.  We also obtain improved bounds on the inverse Turán number of even cycles \nJoint work with Ervin Győri\, Nika Salia and Oscar Zamora.
URL:https://dimag.ibs.re.kr/event/2020-07-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200721T163000
DTEND;TZID=Asia/Seoul:20200721T173000
DTSTAMP:20260424T080950
CREATED:20200519T123058Z
LAST-MODIFIED:20240707T083754Z
UID:2456-1595349000-1595352600@dimag.ibs.re.kr
SUMMARY:Ilkyoo Choi (최일규)\, Flexibility of Planar Graphs
DESCRIPTION:Oftentimes in chromatic graph theory\, precoloring techniques are utilized in order to obtain the desired coloring result. For example\, Thomassen’s proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein\, we investigate a precoloring extension problem formalized by Dvorak\, Norin\, and Postle named flexibility. Given a list assignment $L$ on a graph $G$\, an $L$-request is a function on a subset $S$ of the vertices that indicates a preferred color in $L(v)$ for each vertex $v\in S$. A graph $G$ is $\varepsilon$-flexible for list size $k$ if given a $k$-list assignment $L$ and an $L$-request\, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. We survey known results regarding this new concept\, and prove some new results regarding flexibility of planar graphs.
URL:https://dimag.ibs.re.kr/event/2020-07-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200722T163000
DTEND;TZID=Asia/Seoul:20200722T173000
DTSTAMP:20260424T080950
CREATED:20200629T004204Z
LAST-MODIFIED:20240707T083748Z
UID:2563-1595435400-1595439000@dimag.ibs.re.kr
SUMMARY:Paloma T. Lima\, Graph Square Roots of Small Distance from Degree One Graphs
DESCRIPTION:Given a graph class $\mathcal{H}$\, the task of the $\mathcal{H}$-Square Root problem is to decide whether an input graph G has a square root H that belongs to $\mathcal{H}$. We are interested in the parameterized complexity of the problem for classes $\mathcal{H}$ that are composed by the graphs at vertex deletion distance at most $k$ from graphs of maximum degree at most one. That is\, we are looking for a square root H that has a modulator S of size k such that H-S is the disjoint union of isolated vertices and disjoint edges. We show that different variants of the problems with constraints on the number of isolated vertices and edges in H-S are FPT when parameterized by k\, by providing algorithms with running time $2^{2^{O(k)}}\cdot n^{O(1)}$. We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on k could be avoided. In particular\, we prove that the VC-k Root problem\, that asks whether an input graph has a square root with vertex cover of size at most k\, cannot be solved in time $2^{2^{o(k)}}\cdot n^{O(1)}$ unless the Exponential Time Hypothesis fails. Moreover\, we point out that VC-k Root parameterized by k does not admit a subexponential kernel unless P=NP. \nThis is a joint work with Petr Golovach and Charis Papadopoulos.
URL:https://dimag.ibs.re.kr/event/2020-07-22/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200728T163000
DTEND;TZID=Asia/Seoul:20200728T173000
DTSTAMP:20260424T080950
CREATED:20200708T123952Z
LAST-MODIFIED:20240707T083742Z
UID:2624-1595953800-1595957400@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Solving hard cut problems via flow-augmentation
DESCRIPTION:We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs\, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s\, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t. \nMore precisely\, we consider problems where an (unknown) solution is a set $Z \subseteq E(G)$ of size at most $k$ such that \n\nin $G−Z$\, $s$ and $t$ are indistinct connected components\,\nevery edge of $Z$ connects two distinct connected components of $G − Z$\, and\nif we define the set $Z_{s\,t}\subseteq Z$ as these edges $e \in Z$ for which there exists an (s\, t)-path P_e with $E(P_e) ∩ Z = \{e\}$\, then $Z_{s\,t}$ separates s from t.\n\nWe prove that in the above scenario one can in randomized time $k^O(1)(|V (G)| + |E(G)|)$ add a number of edges to the graph so that with $2^{O(k \log k)}$ probability no added edge connects two components of $G − Z$ and $Z_{s\,t}$ becomes a minimum cut between $s$ and $t$. \nThis additional property becomes a handy lever in applications. For example\, consider the question of an $(s\, t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general\, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s\, t)$-cut in G. Hence\, we immediately obtain that the aforementioned problem admits an $2^{O(k \log k)}n^O(1)$-time randomized fixed-parameter algorithm. \nWe apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below)\, and was unamenable to other techniques for parameterized algorithms in graph cut problems\, such as Randomized Contractions\, Treewidth Reduction or Shadow Removal. \nIn fact\, we go one step further. To demonstrate the power of the approach\, we consider more generally the Boolean Min CSP(Γ)-problems\, a.k.a. Min SAT(Γ)\, parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT\, (2) W[1]-hard\, or (3) able to express the soft constraint (u → v)\, and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate\, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words\, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class\, except those that explicitly encompass directed graph cuts. \nThis is a joint work with Stefan Kratsch\, Marcin Pilipczuk and Magnus Wahlström.
URL:https://dimag.ibs.re.kr/event/2020-07-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200729T163000
DTEND;TZID=Asia/Seoul:20200729T173000
DTSTAMP:20260424T080950
CREATED:20200629T004429Z
LAST-MODIFIED:20240705T200034Z
UID:2567-1596040200-1596043800@dimag.ibs.re.kr
SUMMARY:Akanksha Agrawal\, Polynomial Kernel for Interval Vertex Deletion
DESCRIPTION:Given a graph G and an integer k\, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k\, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by a polynomial function of the parameter. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this talk we look at a sketch of a polynomial kernel for the problem (with the solution size as the parameter). To illustrate one of the key ingredients of our kernel\, we will look at a polynomial kernel for IVD\, when parameterized by the vertex cover number.
URL:https://dimag.ibs.re.kr/event/2020-07-29/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR