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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201203T163000
DTEND;TZID=Asia/Seoul:20201203T173000
DTSTAMP:20260418T105445
CREATED:20201013T135812Z
LAST-MODIFIED:20240705T194003Z
UID:3122-1607013000-1607016600@dimag.ibs.re.kr
SUMMARY:Deniz Sarikaya\, What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs
DESCRIPTION:The study of Hamiltonian graphs\, i.e. finite graphs having a cycle that contains all vertices of the graph\, is a central theme of finite graph theory. For infinite graphs such a definition cannot work\, since cycles are finite. We shall debate possible concepts of Hamiltonicity for infinite graphs and eventually follow the topological approach by Diestel and Kühn [2\,3]\, which allows to generalize several results about being a Hamiltonian graph to locally finite graphs\, i.e. graphs where each vertex has finite degree. An infinite cycle of a locally finite connected graph G is defined as a homeomorphic image of the unit circle $S^1$  in the Freudenthal compactification |G| of G. Now we call G Hamiltonian if there is an infinite cycle in |G| containing all vertices of G. For an introduction see [1]. \nWe examine how to force Hamiltonicity via forbidden induced subgraphs and present recent extensions of results for Hamiltonicity in finite claw-free graphs to locally finite ones. The first two results are about claw- and net-free graphs\, claw- and bull-free graphs\, the last also about further graph classes being structurally richer\, where we focus on paws as relevant subgraphs\, but relax the condition of forbidding them as induced subgraphs. \nThe goal of the talk is twofold: (1) We introduce the history of the topological viewpoint and argue that there are some merits to it (2) sketch the proofs for the results mentioned above in some details. \nThis is based on joint work [4\,5] with Karl Heuer. \nBibliography\n[1] R. Diestel (2017) Infinite Graphs. In: Graph Theory. Graduate Texts in Mathematics\, vol 173. Springer\, Berlin\, Heidelberg. https://doi.org/10.1007/978-3-662-53622-3_8 \n[2] R. Diestel and D. Kühn\, On infinite cycles I\, Combinatorica 24 (2004)\, pp. 69-89. \n[3] R. Diestel and D. Kühn\, On infinite cycles II\, Combinatorica 24 (2004)\, pp. 91-116. \n[4] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls\, arXiv:2006.09160 \n[5] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws\, arXiv:2006.09166
URL:https://dimag.ibs.re.kr/event/2020-12-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201126T100000
DTEND;TZID=Asia/Seoul:20201126T110000
DTSTAMP:20260418T105445
CREATED:20201027T002159Z
LAST-MODIFIED:20240705T193041Z
UID:3195-1606384800-1606388400@dimag.ibs.re.kr
SUMMARY:Da Qi Chen\, Bipartite Saturation
DESCRIPTION:In extremal graph theory\, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number\, sat(n\, H)\, is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov and Erdős\, Hajnal\, and Moon. They also determined the saturation number when H is a clique and classified the extremal structures. \nIn this talk\, we will focus mainly on the bipartite saturation problem (which was also first introduced by Erdős\, Hajnal\, and Moon). Here\, we always assume that both G and H are bipartite graphs. Then\, G is H-saturated if G does not contain H but adding any missing edge across the bipartition creates a copy of H. We can then similarly define sat(n\, H) as the minimum number of edges of an n-by-n bipartite graph that is also H-saturated. One of the most interesting and natural questions here is to determine the saturation number for the complete bipartite graph $K_{s\, t}$. When s=t\, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago\, Gan\, Korandi\, and Sudakov gave an asymptotically tight bound that was only off by an additive constant.  We will highlight the main ideas behind that proof and show\, with some additional techniques\, how the bound can be improved to achieve tightness for the case when s=t-1. \nThis talk is based on collaborative work with Debsoumya Chakraborti and Mihir Hasabnis. See arXiv: https://arxiv.org/abs/2009.07651 for the full paper.
URL:https://dimag.ibs.re.kr/event/2020-11-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201119T163000
DTEND;TZID=Asia/Seoul:20201119T173000
DTSTAMP:20260418T105445
CREATED:20200927T025647Z
LAST-MODIFIED:20240705T194022Z
UID:3062-1605803400-1605807000@dimag.ibs.re.kr
SUMMARY:Yijia Chen (陈翌佳)\, Graphs of bounded shrub-depth\, through a logic lens
DESCRIPTION:Shrub-depth is a graph invariant often considered as an extension\nof tree-depth to dense graphs. In this talk I will explain our recent\nproofs of two results about graphs of bounded shrub-depth. \n\nEvery graph property definable in monadic-second order logic\,\ne.g.\, 3-colorability\, can be evaluated by Boolean circuits of constant\ndepth and polynomial size\, whose depth only depends on the\nshrub-depth of input graphs.\nGraphs of bounded shrub-depth can be characterized by\na finite set of forbidden induced subgraphs [Ganian et al. 2015].\n\nCentral to the first result is the definability in first-order logic of\ntree-models for graphs of bounded shrub-depth. For the second\nresult\, we observe that shrub-depth can be easily generalized\nto infinite graphs\, and thus some classical tools\, i.e.\, Craig’s\nInterpolation and Łoś-Tarski Theorem\, in model theory are\napplicable to graphs of bounded shrub-depth. \nThis is joint work with Jörg Flum.
URL:https://dimag.ibs.re.kr/event/2020-11-19/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201111T163000
DTEND;TZID=Asia/Seoul:20201111T173000
DTSTAMP:20260418T105445
CREATED:20200927T024800Z
LAST-MODIFIED:20240707T082419Z
UID:3059-1605112200-1605115800@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Constant congestion bramble
DESCRIPTION:In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk\, Paweł Komosa and Manuel Sorge. \nA bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. \nBrambles are objects dual to treewidth: As shown by Seymour and Thomas\, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However\, as shown by Grohe and Marx\, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0\,\frac{1}{2}]$. On the other hand\, the combination of results of Grohe and Marx\, and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{O}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{O}$ hide polylogarithmic factors and divisors\, respectively.) \nWe first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2})$ and congestion $2$\, i.e.\, every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second\, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $\delta \in (0\,\frac{1}{2}]$\, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2+\delta})$ and size $2^{\widetilde{O}(k^{2\delta})}$.
URL:https://dimag.ibs.re.kr/event/2020-11-11/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201105T100000
DTEND;TZID=Asia/Seoul:20201105T110000
DTSTAMP:20260418T105445
CREATED:20200818T142112Z
LAST-MODIFIED:20240707T082448Z
UID:2820-1604570400-1604574000@dimag.ibs.re.kr
SUMMARY:Daniel Cranston\, Vertex Partitions into an Independent Set and a Forest with Each Component Small
DESCRIPTION:For each integer $k\ge 2$\, we determine a sharp bound on\n$\operatorname{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$\, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most k vertices. For each $k$ we construct an infinite family of examples showing our result is best possible. Hendrey\, Norin\, and Wood asked for the largest function $g(a\,b)$ such that if $\operatorname{mad}(G) < g(a\,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $\operatorname{mad}(G[A]) < a$ and $\operatorname{mad}(G[B]) < b$. They specifically asked for the value of $g(1\,b)$\, which corresponds to the case that $A$ is an independent set. Previously\, the only values known were $g(1\,4/3)$ and $g(1\,2)$. We find the value of $g(1\,b)$ whenever $4/3 < b < 2$. This is joint work with Matthew Yancey.
URL:https://dimag.ibs.re.kr/event/2020-11-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201022T101000
DTEND;TZID=Asia/Seoul:20201022T111000
DTSTAMP:20260418T105445
CREATED:20200927T024614Z
LAST-MODIFIED:20240705T194022Z
UID:3056-1603361400-1603365000@dimag.ibs.re.kr
SUMMARY:Chun-Hung Liu (劉俊宏)\, Asymptotic dimension of minor-closed families and beyond
DESCRIPTION:The asymptotic dimension of metric spaces is an important notion in  geometric group theory. The metric spaces considered in this talk are  the ones whose underlying spaces are the vertex-sets of (edge-)weighted  graphs and whose metrics are the distance functions in weighted graphs.  A standard compactness argument shows that it suffices to consider the  asymptotic dimension of classes of finite weighted graphs. We prove that  the asymptotic dimension of any minor-closed family of weighted graphs\,  any class of weighted graphs of bounded tree-width\, and any class of  graphs of bounded layered tree-width are at most 2\, 1\, and 2\,  respectively. The first result solves a question of Fujiwara and  Papasoglu; the second and third results solve a number of questions of  Bonamy\, Bousquet\, Esperet\, Groenland\, Pirot and Scott. These bounds for  asymptotic dimension are optimal and generalize and improve some results  in the literature\, including results for Riemannian surfaces and Cayley  graphs of groups with a forbidden minor.
URL:https://dimag.ibs.re.kr/event/2020-10-22/
LOCATION:Zoom ID:95464969835 (356260)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200924T100000
DTEND;TZID=Asia/Seoul:20200924T110000
DTSTAMP:20260418T105445
CREATED:20200811T231744Z
LAST-MODIFIED:20240707T082720Z
UID:2781-1600941600-1600945200@dimag.ibs.re.kr
SUMMARY:Zihan Tan\, Towards Tight(er) Bounds for the Excluded Grid Theorem
DESCRIPTION:We study the Excluded Grid Theorem\, a fundamental structural result in graph theory\, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f$\, such that for every integer $g > 0$\, every graph of treewidth at least $f(g)$ contains the g×g-grid as a minor. For every integer $g > 0$\, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order $g^2 \log g$. For a long time\, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g) = O(g^{98} \operatorname{poly log} g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36} \operatorname{poly log} g)$\, and then to $f(g) = O(g^{19} \operatorname{poly log} g)$. In this talk\, we present our recent work that further improves this bound to $f(g) = O(g^9 \operatorname{poly log} g)$ via a simpler proof. Moreover\, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem\, it seems conceivable that the techniques proposed in this talk can lead to even tighter bounds on $f(g)$. \nThis talk is based on joint work with Julia Chuzhoy.
URL:https://dimag.ibs.re.kr/event/2020-09-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200917T100000
DTEND;TZID=Asia/Seoul:20200917T110000
DTSTAMP:20260418T105445
CREATED:20200811T231948Z
LAST-MODIFIED:20240707T082734Z
UID:2789-1600336800-1600340400@dimag.ibs.re.kr
SUMMARY:Luke Postle\, Further progress towards Hadwiger's conjecture
DESCRIPTION:In 1943\, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s\, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  Recently\, Norin\, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$\, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically\, they are $O(t (\log \log t)^{6})$-colorable.
URL:https://dimag.ibs.re.kr/event/2020-09-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200910T171000
DTEND;TZID=Asia/Seoul:20200910T181000
DTSTAMP:20260418T105445
CREATED:20200708T123031Z
LAST-MODIFIED:20240705T200015Z
UID:2619-1599757800-1599761400@dimag.ibs.re.kr
SUMMARY:Sebastian Siebertz\, Rank-width meets stability
DESCRIPTION:Forbidden graph characterizations provide a convenient way of specifying graph classes\, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded tree-width\, which are characterized as those classes that exclude some planar graph as a minor. Similarly\, in model theory\, classes of structures are characterized by configurations that are forbidden as logical interpretations or transductions. Two notions from classical model theory are (monadic) stability and (monadic) dependence\, which correspond to the impossibility of interpreting with first-order logic (after a vertex coloring step) arbitrary long linear orders and all graphs\, respectively.  Examples of monadically stable classes of graphs are nowhere dense graph classes\, and examples of monadically dependent classes are classes of bounded rank-width (or equivalently\, bounded clique-width)\, which can be seen as a dense analog of classes of bounded tree-width. \nI will give an overview over recent approaches to combine model theoretic and graph theoretic tools to derive structural and algorithmic results for classes of (finite) graphs. I assume no background from logic.
URL:https://dimag.ibs.re.kr/event/2020-09-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200826T103000
DTEND;TZID=Asia/Seoul:20200826T113000
DTSTAMP:20260418T105445
CREATED:20200629T004929Z
LAST-MODIFIED:20240705T200027Z
UID:2576-1598437800-1598441400@dimag.ibs.re.kr
SUMMARY:Nick Brettell\, On the graph width parameter mim-width
DESCRIPTION:Maximum induced matching width\, also known as mim-width\, is a width parameter for graphs introduced by Vatshelle in 2012.  This parameter can be defined over branch decompositions of a graph G\, where the width of a vertex partition (X\,Y) in G is the size of a maximum induced matching in the bipartite graph induced by edges of G with one endpoint in X and one endpoint in Y.  In this talk\, I will present a quick overview of mim-width and some key results that highlight why this parameter is of interest from both a theoretical and algorithmic point of view.  I will discuss some recent work regarding the boundedness or unboundedness of mim-width for hereditary classes defined by forbidding one or two induced subgraphs\, and for generalisations of convex graphs.  I will also touch on some interesting applications of this work\, in particular for colouring and list-colouring.  This is joint work with Jake Horsfield\, Andrea Munaro\, Giacomo Paesani\, and Daniel Paulusma.
URL:https://dimag.ibs.re.kr/event/2020-08-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200819T163000
DTEND;TZID=Asia/Seoul:20200819T173000
DTSTAMP:20260418T105445
CREATED:20200629T004729Z
LAST-MODIFIED:20240705T200030Z
UID:2573-1597854600-1597858200@dimag.ibs.re.kr
SUMMARY:Gwenaël Joret\, Packing and covering balls in graphs excluding a minor
DESCRIPTION:In 2007\, Chepoi\, Estellon\, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$\, and every planar graph $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$\, or there is a subset of vertices of size at most $c k$ meeting all balls of radius $r$ in $G$. The key aspect of this conjecture is that the constant $c$ does not depend on the radius $r$ of the balls. If we were to allow this dependency\, then the statement is known to hold\, and in fact it is true in the more general setting of graph classes with bounded expansion (as proved by Dvořák). \nIn this talk I will present a proof of this conjecture. The result we prove is a bit more general: (1) The conjecture holds for every proper minor-closed class of graphs (with the constant $c$ depending on the class)\, and (2) we can even focus on any set of balls in the graph we like\, there is nothing special about taking all balls of a given radius. In other words\, we show that for every proper minor-closed class $C$ of graphs\, there exists a constant $c>0$ such that for every graph $G$ in $C$\, every set $S$ of balls in $G$\, and every positive integer $k$\, either there are $k$ vertex-disjoint balls in $S$\, or there is a subset of vertices of $G$ of size at most $c k$ meeting all balls in $S$. \nJoint work with Nicolas Bousquet\, Wouter Cames van Batenburg\, Louis\nEsperet\, William Lochet\, Carole Muller\, and François Pirot.
URL:https://dimag.ibs.re.kr/event/2020-08-19/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200805T163000
DTEND;TZID=Asia/Seoul:20200805T173000
DTSTAMP:20260418T105445
CREATED:20200629T004613Z
LAST-MODIFIED:20240705T200032Z
UID:2570-1596645000-1596648600@dimag.ibs.re.kr
SUMMARY:Robert Ganian\, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
DESCRIPTION:Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete\, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this talk is to summarize these recent developments and put them into context. Special attention will be paid to the structural parameter treedepth\, and at the end of the talk we will also consider how treedepth can be used to design algorithms for problems beyond ILP.
URL:https://dimag.ibs.re.kr/event/2020-08-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200729T163000
DTEND;TZID=Asia/Seoul:20200729T173000
DTSTAMP:20260418T105445
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200722T163000
DTEND;TZID=Asia/Seoul:20200722T173000
DTSTAMP:20260418T105446
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
END:VCALENDAR