Speaker

Eunjung Kim

Title

Flow-augmentation Technique and Its Applications

Abstract

We present a technique called the flow-augmentation and review how the technique can be used for designing graph cut problems. The flow-augmentation algorithm is a randomized polynomial-time algorithm, given a directed graph G, two vertices s and t, and an integer k, which adds a number of arcs so that for every minimal st-cut Z in G of size at most k, Z becomes an minimum st-cut in the resulting graph with probability 2^{-poly(k)}. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: (1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as Weighted st-Cut or Weighted Directed Feedback Vertex Set. Furthermore, leveraging the directed flow-augmentation technique, we obtain a complete dichotomy theorem for Boolean CSPs parameterized by the number of unsatisfied constraints. The talk is based on a series of joint work with Stefan Kratsch, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström.

Bio

Eunjung KIM obtained her PhD in 2010 from Royal Holloway, University of London. After post-doctoral fellowship at LIRMM-CNRS in France, she was a researcher at CNRS (National Center for Scientific Research, France) between 2011 and 2023. Since 2024, she is an associate professor at KAIST. Dr. Kim contributed some important results in the study of algorithms using structural graph theory and width parameters. Among those, she is one of the researchers who invented the notion of twin-width in 2020, which is now used widely and considered an important tool for algorithms design, logic, structural graph theory and so on. She is one of the authors who proposed the flow-augmentation technique, which was essential for resolving some long open problems in parameterized complexity. She is awarded with the CNRS bronze medal, which is given to an early-career researcher in each field of basic science in France as a recognition of research excellence and leadership.

Language

English