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:20200722T163000
DTEND;TZID=Asia/Seoul:20200722T173000
DTSTAMP:20260423T094003
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