김은정

Archive of posts with tag '김은정'

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

    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.

    Tags:

  • Eun Jung Kim, Tree-cut width: computation and algorithmic applications
    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.
    Tags:

  • Eunjung Kim, A polynomial-time algorithm for outerplanar diameter improvement
    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.
    Tags:

  • Eunjung Kim (김은정), On subexponential and FPT-time inapproximability
    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.

    Tags:

  • Eun Jung Kim (김은정), Linear kernels and single-exponential algorithms via protrusion decompositions
    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.
    Tags:

  • Eun-Jung Kim (김은정), Solving MAX-r-SAT above a Tight Lower Bound
    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.

    Tags:

  • Eun Jung Kim (김은정), Fixed-Parameter Tractability and Parameterized Minimum Leaf Out-Branching Problems
    Fixed-Parameter Tractability and Parameterized Minimum Leaf Out-Branching Problems
    Eun Jung Kim (김은정)
    Dept. of Computer Science, Royal Holloway, University of London, Egham, UK.
    2008/04/17 Thu, 3PM-4PM

    Fixed-Parameter Tractability (FPT) is a rapidly expanding framework to tackle computationaly hard problems. In many combinatorial problems, the input instance usually comes in pair with an interger k, of which the typical example is found in the VERTEX COVER: Given a graph G and an integer k, is there a VERTEX COVER of size at most k? The motivation is to restrict the presumably inevitable combinatorial explosion to be one in terms of k so that for a relatively small k the problem is expected to be solved in a reasonable amount time. Moreover paramterized framework leads to an elaborate hierarchy of computational compelxity which is analogous to the traditional complexity classes.

    Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We describe three parameterizations of MinLOB and prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parametrization is as follows: given a digraph D and a positive integral parameter k, check whether D contains an out-branching with at least k non-leaves (and find such an out-branching if it exists).

    Tags:

Monthly Archives