Loading Events

« All Events

  • This event has passed.
:

Paloma T. Lima, Graph Square Roots of Small Distance from Degree One Graphs

Wednesday, July 22, 2020 @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

Paloma T. Lima
IT University of Copenhagen
http://itu.dk/~palt/

Given a graph class H, the task of the H-Square Root problem is to decide whether an input graph G has a square root H that belongs to H. We are interested in the parameterized complexity of the problem for classes 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 22O(k)nO(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 22o(k)nO(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.

This is a joint work with Petr Golovach and Charis Papadopoulos.

Details

Date:
Wednesday, July 22, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.