• This event has passed.

Manuel Lafond, Recognizing k-leaf powers in polynomial time, for constant k

February 18 Friday @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G), and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology, but recognizing them has remained a challenging algorithmic problem for the past two decades. In a recent paper presented at SODA22, it was shown that k-leaf powers can be recognized in polynomial time if k is fixed.

In this seminar, I will present the algorithm that decides whether a graph G is a k-leaf power in time $O(n^{f(k)})$ for some function f that depends only on k (but has the growth rate of a power tower function). More specifically, I will discuss how the difficult k-leaf power instances contain many cutsets that have the same neighborhood layering. I will then show that these similar cutsets are redundant and that removing one of them does not lose any information, which can be exploited for algorithmic purposes.

Details

Date:
February 18 Friday
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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