Loading Events

« All Events

  • This event has passed.

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

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

Zoom ID: 869 4632 6610 (ibsdimag)

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.


Friday, February 18, 2022
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:


Zoom ID: 869 4632 6610 (ibsdimag)


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.