Posts Tagged ‘김은정’

Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality

Monday, December 17th, 2018

IBS/KAIST Joint Discrete Math Seminar

New algorithm for multiway cut guided by strong min-max duality
Eun Jung Kim (김은정)
CNRS, LAMSADE, Paris, France
2019/01/04 Fri 4PM-5PM (Room: DIMAG, IBS)

Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design.

In this talk, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds, namely μ(I)=2LP(I)-IP(dual-I). Here, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result, we obtain an algorithm running in time 4k-μ(I)for multiway cut and its generalizations, where k is the budget for a solution.

This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.

Eun Jung Kim, Tree-cut width: computation and algorithmic applications

Friday, February 27th, 2015
Tree-cut width: computation and algorithmic applications
Eun Jung Kim
CNRS, LAMSADE, Paris, France
2015/3/17 Tue 4PM-5PM
Wollan has recently introduced the graph parameter tree-cut width, which plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems which are not believed to be fixed-parameter tractable (FPT) when parameterized by treewidth.
We present a 2-approximation fpt-algorithm for the problem of deciding whether the tree-cut width is at most k: that is, given a graph G and a positive integer k, the algorithm correctly decides in time 2O(k2 log k)·n5 log n that the tree-cut width of G is strictly bigger than k, or returns a tree-cut decomposition whose width is at most 2k. Moreover, we develop the notion of nice tree-cut decompositions and show that any tree-cut decomposition can be transformed into a nice one in polynomial time. Based on this notion, we introduce a general three-stage dynamic framework for the design of FPT algorithms on nice tree-cut decompositions and apply it to several classic problems.
This talk is based on two recent works with Robert Ganian, Stefan Szeider, Sang-il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos.

Eunjung Kim, A polynomial-time algorithm for outerplanar diameter improvement

Tuesday, March 4th, 2014
A polynomial-time algorithm for outerplanar diameter improvement
Eunjung Kim
CNRS, LAMSADE, Paris, France
2014/05/26 Monday 4PM-5PM
Room 1409
The Outerplanar Diameter Improvement problem asks, given a graph G and an integer D, whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.

Eunjung Kim (김은정), On subexponential and FPT-time inapproximability

Monday, November 18th, 2013
On subexponential and FPT-time inapproximability
Eunjung Kim
CNRS, LAMSADE, Paris, France
2013/12/18 Wednesday 4PM-5PM
Room 1409

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once allowed with subexponential-time or FPT-time is a central question. Recently, several independent results appeared regarding this question, implying negative answer toward the conjecture. They state that, for every 0<r<1, there is no r-approximation which runs in better than certain subexponential-function time. We outline the results in these papers and overview the important concepts and techniques used to obtain such results.

Eun Jung Kim (김은정), Linear kernels and single-exponential algorithms via protrusion decompositions

Sunday, September 16th, 2012
Linear kernels and single-exponential algorithms via protrusion decompositions
Eun Jung Kim (김은정)
CNRS, LAMSADE, Paris, France.
2012/10/19 Fri 4PM-5PM
A t-treewidth-modulator of a graph G is a set X⊆V(G) such that the treewidth of G-X is at most some constant t-1. In this paper, we present a novel algorithm to compute a decomposition scheme for graphs G that come equipped with a t-treewidth-modulator. This decomposition, called a protrusion decomposition, is the cornerstone in obtaining the following two main results.
We first show that any parameterized graph problem (with parameter k) that has finite integer index and is treewidth-bounding admits a linear kernel on H-topological-minor-free graphs, where H is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a t-treewidth-modulator of size O(k), for some constant t. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and H-minor-free graphs [Fomin et al., SODA 2010].
Our second application concerns the Planar-F-Deletion problem. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, Planar-F-Deletion asks whether G has a set X⊆ V(G) such that |X|≤k and G-X is H-minor-free for every H∈F. Very recently, an algorithm for Planar-F-Deletion with running time 2O(k) n log2 n (such an algorithm is called single-exponential) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in F is connected. Using our algorithm to construct protrusion decompositions as a building block, we get rid of this connectivity constraint and present an algorithm for the general Planar-F-Deletion problem running in time 2O(k)n2.
This is a joint work with Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar.