Posts Tagged ‘김은정’

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.

Eun-Jung Kim (김은정), Solving MAX-r-SAT above a Tight Lower Bound

Monday, December 21st, 2009
Solving MAX-r-SAT above a Tight Lower Bound
Eun Jung Kim (김은정)
Dept. of Computer Science, Royal Holloway, University of London, Egham, UK.
2009/12/23 Wed, 4PM-5PM (Room 2411)

We consider the problem Max-r-SAT, an extensively studied variant of the classic satisfiability problem. Given an instance of CNF (Conjunctive normal form) in which each clause consists of exactly r literals, we seek to find a satisfying truth assignment that maximizes the number of satisfied clauses. Even when r=2, the problem is intractable unless P=NP. Hence the next quest is how close we can get to optimality with moderate usage of computation time/space.

We present an algorithm that decides, for every fixed r≥2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r-1)m+k)/2r clauses. Our algorithm is based on a polynomial-time preprocessing procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k2) variables. Moreover, by combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that an instance of Max-2-Sat either is a YES-instance or can be transformed into an equivalent instance of size at most 3k.

This is a joint work with Noga Alon, Gregory Gutin, Stefan Szeider, and Anders Yeo.