EUNJUNG KIM

Since January 2024, I am an associate professor at School of Computing, KAIST

Contact

  • Email: eunjungkim78 at gmail.com
  • Address: Office E3406, E3-1 School of Computing, KAIST, Daehak-ro 291, Daejeon, South Korea.
I obtained the master's degree in industrial engineering at KAIST, South Korea and PhD degree in computer science at Royal Holloway, University of London in UK, 2010.
I was a postdoc at Project Team ALGCo, CNRS-LIRMM in 2010-2011. From 2011 October till December 2023, I was a CNRS researcher (chargé de recherche), hosted at LAMSADE, from which I am taking a temporary leave.

Research Interests

  • Fixed-Parameter Algorithms and lower bound
  • Constraint Satisfaction Problems
  • Graph Theory and structure, width parameters
  • Linear matroids and algorithmic applications

Research Grant

  • A principal investigator of ANR JCJC project ASSK (ANR-18-CE40-0025-01).
  • A local coordinator of ANR project ESIGMA(ANR-17-CE23-0010).

Publications

  1. Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström,
    On weighted graph separation problems and flow-augmentation,
    In SIAM Journal on Discrete Mathematics (SIDMA).

  2. Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, Manolis Vasilakis,
    Bandwidth Parameterized by Cluster Vertex Deletion Number,
    In the International Symposium on Parameterized and Exact Computation (IPEC 2023).

  3. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström,
    Flow-augmentation III: complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints, arxiv
    In the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).

  4. Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes and Stéphan Thomassé
    Twin-width VIII: delineation and win-wins, arxiv
    The proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2022).

  5. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström,
    Directed flow-augmentation, arxiv
    The proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022).

  6. Mamadou Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum,
    Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k, arxiv
    conference version: the proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
    journal version: Journal of Combinatorial Theory B 160, pp.15-35 (2023)

  7. Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé,
    Twin-width VI: the lens of contraction sequences,arxiv
    In the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)

  8. Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigan,
    Twin-width and polynomial kernels, arxiv
    conference version: the proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2021).

  9. Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos,
    A Constant-factor Approximation for Weighted Bond Cover, arxiv
    In the proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2021).

  10. Eun Jung Kim, Martin Milanic, Jérôme Monnot, Christophe Picouleau
    Complexity and algorithms for constant diameter augmentation problems arxiv
    Theoretical Computer Science, 2021.

  11. Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon
    On the tree-width of even-hole-free graphs, arxiv
    European Journal of Combinatorics, 2021.

  12. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
    Twin-width III: Max Independent Set and Coloring
    In the proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2021) arxiv

  13. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
    Solving hard cut problems via flow-augmentation
    conference version: In the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) arxiv
    journal version: To appear in ACM Transactions on Algorithms.

  14. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
    Twin-width II: small classes
    conference version: the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) arxiv
    journal version: Combinatorial Theory 2 (2), 2022.

  15. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
    Twin-width I: tractable FO model checking arxiv.
    conference version: the proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)
    journal version: Journal of ACM ACM 69 (1), pp.1-46 (2022).

  16. Jungho Ahn, Eun Jung Kim and Euiwoong Lee,
    Towards constant-factor approximation for chordal / distance-hereditary vertex deletion arxiv.
    conference version: the proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020)
    journal version: Algorithmica 84 (7), pp. 2106-2133 (2022).

  17. Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou and Yota Otachi,
    Grundy Distinguishes Treewidth from Pathwidth
    conference version: the proceeding of the European Symposium on Algorithms (ESA 2020) arxiv.
    journal version: SIAM Journal on Discrete Mathematics 36 (3), 2022.

  18. Pierre Aboulker, Edouard Bonnet, Eun Jung Kim, Florian Sikora,
    Grundy Coloring & friends, Half-Graphs, Bicliques arxiv.
    conference version: the proceeding of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
    journal version: Algorithmica 85, pp. 1-28 (2023).

  19. Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi and Florian Sikora,
    Token Sliding on Split Graphs
    conference version: the proceeding of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
    journal version: Theory of Computing Systems, 2020. arxiv

  20. Eun Jung Kim, Maria Serna, Dimitrios M. Thilikos,
    Data-compression for Parametrized Counting Problems on Sparse graphs
    conference version: the proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018) arxiv

  21. Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider,
    Weighted Counting for Constraint Satisfaction with Default Values: Algorithms and Complexity Results
    conference version: the proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI 2018)
    journal version ("Sum-of-Products with Default Values: Algorithms and Complexity Results"): Journal of Artificial Intelligence Research (JAIR) 73, pp. 535-552, 2020.

  22. Remy Belmonte, Tesshu Hanaka, Ionnis Katsikarelis, Eun Jung Kim, Michael Lampis,
    New Results on Directed Edge Dominating Set
    conference version: the proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) arxiv

  23. Jisu Jeong, Eun Jung Kim, Sang-il Oum, Finding branch-decompositions of matroids, hypergraphs, and more
    conference version: the proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018) arxiv
    journal version: SIAM Journal on Discrete Mathematics (SIDMA), 2021

  24. Edouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzcazewski and Florian Sikora
    QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
    conference version: the proceedings of the International Symposium on Computational Geometry (SoCG 2018) arxiv
    journal version: expanded paper "EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs" additionally with Marthe Bonamy, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé: Journal of the ACM (2020)

  25. E. J. Kim and O-Joung Kwon, Erdos-Posa property of chordless cycles and its applications
    conference version: the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
    journal version: Journal of Combinatorial Theory B, 2020. arxiv

  26. Eun Jung Kim, O-joung Kwon, A Polynomial Kernel for Distance-Hereditary Vertex Deletion
    conference version: the proceedings of the Workshop on Algorithms and Data Structures (WADS 2017) arxiv
    journal version: Algorithmica (2021)

  27. Jisu Jeong, Eun Jung Kim, Sang-il Oum, Constructive algorithm for path-width of matroids
    conference version: the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) arxiv
    journal version: IEEE Trans. Information Theory 63(11): 7178-7205 (2017)

  28. E. J. Kim, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
    Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
    conference version: the proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) arxiv
    journal version: Comput. Syst. Sci. 86: 191-206 (2017)

  29. Holger Dell, E. J. Kim, Michael Lampis, Valia Mitsou and Tobias Momke
    Complexity and Approximability for Parameterized CSPs
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) arxiv
    journal version: Algorithmica 79(1): 230-250 (2017)

  30. E. J. Kim and O-Joung Kwon, A polynomial kernel for Block Graph Deletion
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). arxiv
    journal version: Algorithmica 79(1): 251-270 (2017)

  31. Mamadou Kanté, E. J. Kim, O-Joung Kwon and Christophe Paul,
    An FPT algorithm and a polynomial kernel for Linear Rankwidth One Vertex Deletion
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). arxiv
    journal version: Algorithmica 79(1): 66-95 (2017)

  32. E. J. Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
    An FPT 2-Approximation for Tree-Cut Decomposition
    conference version: Proceedings of 13th Workshop on Approximation and Online Algorithms (WAOA 2015). arxiv
    journal version: Algorithmica 80 (1): 116--135 (2018)

  33. Robert Ganian, E. J. Kim and Stefan Szeider, Algorithmic Applications of Tree-Cut Width
    Proceedings of the 40th Mathematical Foundations of Computer Science (MFCS 2015)

  34. E. J. Kim, Martin Milanic and Oliver Schaudt, Recognizing k-equistable graphs in FPT time
    Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015). arxiv

  35. Edouard Bonnet, Florent Foucaud, E. J. Kim, Florian Sikora, Complexity of Grundy coloring and its variants
    conference version: Proceedings of the 21st International Computing and Combinatorics Conference (COCOON 2015). arxiv
    journal version: Discrete Applied Mathematics 2018.

  36. N. Cohen, D. Goncalves, E. J. Kim, C. Paul, I. Sau, D. Thilikos, M. Weller,
    A Polynomial-time Algorithm for Outerplanar Diameter Improvement,
    conference version: the Proceedings of the 10th International Computer Science Symposium in Russia (CSR 2015). arxiv
    journal version: J. Comput. Syst. Sci. 89: 315-327 (2017)

  37. R. Crowston, M. Fellows, G. Gutin, M. Jones, E. J. Kim, F. Rosamond, I. Z. Ruzsa, S. Thomasse, A. Yeo,
    Satisfying More Than Half Linear Equations Over F2: A multivariate approach
    Journal of Computer and System Sciences. 80 (4), pp. 687-696, 2014. arxiv

  38. E. Bonnet, B. Escoffier, E. J. Kim, V. Paschos, On Subexponential and FPT-time Inapproximability,
    conference version: Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013). arxiv
    journal version: Algorithmica 71 (3), pp. 541-656, 2015.

  39. E. J. Kim, Sebastian Ordyniak, Stefan Szeider,
    The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation,
    Proceedings of the 2nd International Workshop on Theory and Applications of Formal Argumentation (TAFA 2013).

  40. E. J. Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar,
    Linear kernels and single-exponential algorithms via protrusion decompositions,
    conference version: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013). arxiv
    journal version: ACM Transactions on Algorithms (TALG) 12 (2), 2016.

  41. Daniel Goncalves, E. J. Kim, On Exact Algorithms for Permutation CSP
    Theoretical Computer Science. 511, pp. 109-116, 2013. arxiv

  42. E. J. Kim, Sebastian Ordyniak, Valued-Based Argumentation for Tree-like Value Graphs
    Proceedings of the 4th International Conference on Computational Models of Argument (COMMA 2012) pdf

  43. E. J. Kim, Christophe Paul, Geevarghese Philip, A single-exponential FPT algorithm for K4-minor cover problem
    conference version: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012). arxiv
    journal version: Journal of Computer and System Sciences 81 (1), pp. 186-207, 2015.

  44. S. Gaspers, S. Szeider, S. Ordyniak, E.J. Kim, S. Saurabh, Don't Be Strict in Local Search!
    Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12). arxiv

  45. E. J. Kim, R. Williams, Improved Parameterized Algorithms for Above Average Constraint Satisfaction,
    Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC 2011). arxiv

  46. G. Gutin, E. J. Kim, M. Lampis, V. Mitsou, Vertex Cover Problem Parameterized Above and Below Tight Bounds,
    Theory of Computing Systems 48 (2), pp. 402-410, 2011. arxiv

  47. G. Gutin, E. J. Kim, A. Soleimanfallah, S. Szeider, A. Yeo, Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming,
    conference version: the 5th International Symposium on Parameterized and Exact Computation (IPEC 2010). pdf
    journal version: Algorithmica 64 (1), pp. 112-125, 2012.

  48. E. J. Kim, S. Ordyniak, S. Szeider, Complexity Results for Argumentation and Subjective Acceptance
    conference version: the 3rd International Conference on Computational Models of Argument (COMMA 2010).
    journal version: Artificial Intelligence 175 (9--10), pp. 1722-1736, 2011. arxiv

  49. G. Gutin, E. J. Kim, M. Mnich, A. Yeo, Betweenness Parameterized Above Tight Lower Bound,
    Journal of Computer and System Sciences 76 (8), pp. 872--878, 2010. arxiv

  50. R. Crowston, G. Gutin, M. Jones, E. J. Kim, I.Z. Ruzsa, Systems of Linear Equations over F_2 and Problems Parameterized Above Average
    Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010). arxiv

  51. N. Alon, G. Gutin, E. J. Kim, S. Szeider, A. Yeo, Solving Max r-SAT Above a Tight Lower Bound
    conference version: the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
    journal version: Algorithmica 61 (3), pp. 638-655, 2011. arxiv

  52. J. Daligault, G. Gutin, E. J. Kim, A. Yeo, FPT Algorithms and Kernels for the Directed k-Leaf Problem,
    Journal of Computer and System Sciences 76 (2), pp. 144-152, 2010. arxiv

  53. A. Gupta, G. Gutin, M. Karimi, E. J. Kim, A. Rafiey, Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-transitive Digraphs
    Australasian Journal of Combinatorics 46, pp. 217-232, 2010. arxiv

  54. G. Gutin, E. J. Kim, The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops,
    Discrete Applied Mathematics 158 (4), pp. 319-330, 2010. arxiv

  55. G. Gutin, E. J. Kim, S. Szeider, A. Yeo, A Probabilistic Approach To Problems Parameterized Above Tight Lower Bound,
    conference version: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009). arxiv
    journal version: Journal of Computer and System Sciences 77 (2). pp. 422-429, 2011.

  56. N. Cohen, F. V. Fomin, G. Gutin, E. J. Kim, S. Saurabh, A. Yeo, Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem.
    conference version: Proceedings of the 15th International Computing and Combinatorics Conference (COCOON 2009). pdf
    journal version: Journal of Computer and System Sciences 76 (7), pp. 650-662, 2010.

  57. P. Dunkelmann, G. Gutin, E. J. Kim, On the Complexity of Minimum Leaf Out-branching Problem,
    Discrete Applied Mathematics     157 (13), pp. 3000-3004, 2009. arxiv

  58. G. Gutin, E. J. Kim, I. Razgon, Minimum Leaf Out-branching and Related Problems,
    conference version: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008).
    journal version: Theoretical Computer Science 410 (45), pp. 4571-4579, 2009. arxiv

  59. A. Gupta, M. Karimi, E. J. Kim, A. Rafiey, Minimum Cost Homomorphisms to Locally In-semicomplete Digraphs,
    Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2008). pdf

  60. G. Gutin, E. J. Kim, Properly Coloured Cycles and Paths: Results and Open Problems,
    LNCS Proceedings of the conference honoring Martin Golumbic's 60th birthday, 2008.

  61. G. Gutin, E. J. Kim, Introduction to the Minimum Cost Homomorphism Problem for Directed and Undirected Graphs,
    Lecture Notes of Ramanujan Mathematical Society 7, pp. 25-37, 2008. preprint-pdf

Thesis

  • PhD thesis: Parameterized Algorithms on Digraph and Constraint Satisfaction Problems (pdf) supervised by Gregory Gutin

Teaching

  • Exact resolution of NP-hard problems, 2021 Spring; joint lecture with Michael Lampis.

  • Computability and Complexity, 2020 Fall.

  • Exact Resolution of NP-hard problems, 2019 Spring; joint lecture with Michael Lampis.

Last update: 1 Feb 2024