I did the master's degree at KAIST,
South Korea and completed the PhD study in theoretical computer
science at Royal Holloway,
University of London in UK, 2010. I was a postdoc at Project
Team ALGCo, CNRSLIRMM
in 20102011.
Research Interests
 FixedParameter Algorithms and lower bound
 Constraint Satisfaction Problems
 Graph Theory and structure, width parameters
Publications
 Jisu Jeong, Eun Jung Kim, Sangil Oum, Constructive algorithm for pathwidth of matroids
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA 2016)
arxiv
 E. J. Kim, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
Parameterized Algorithms for MinMax Multiway Cut and List Digraph Homomorphism
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
arxiv
 Holger Dell, E. J. Kim, Michael Lampis, Valia Mitsou and Tobias Momke
Complexity and Approximability for Parameterized CSPs
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
arxiv
 E. J. Kim and OJoung Kwon, A polynomial kernel for Block Graph Deletion
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015).
arxiv
 Mamadou Kante, E. J. Kim, OJoung Kwon and Christophe Paul,
An FPT algorithm and a polynomial kernel for Linear Rankwidth One Vertex Deletion
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015).
arxiv
 E. J. Kim, SangIl Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
An FPT 2Approximation for TreeCut Decomposition
Proceedings of 13th Workshop on Approximation and Online Algorithms (WAOA 2015).
arxiv
 Robert Ganian, E. J. Kim and Stefan Szeider, Algorithmic Applications of TreeCut Width
Proceedings of the 40th Mathematical Foundations of Computer Science (MFCS 2015)
 E. J. Kim, Martin Milanic and Oliver Schaudt, Recognizing kequistable graphs in FPT time
Proceedings of the 41st International Workshop on GraphTheoretic Concepts in Computer Science (WG 2015).
arxiv
 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
 N. Cohen, D. Goncalves, E. J. Kim, C. Paul, I. Sau, D. Thilikos, M. Weller,
A Polynomialtime Algorithm for Outerplanar Diameter Improvement,
conference version: Proceedings of the Proceedings of the 10th International Computer Science Symposium
in Russia (CSR 2015).
arxiv
 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. 687696, 2014. arxiv
 E. Bonnet, B. Escoffier, E. J. Kim, V. Paschos, On Subexponential and FPTtime Inapproximability,
conference version: Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013).
arxiv
journal version: Algorithmica 71 (3), pp. 541656, 2015.

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).
 E. J. Kim, Alexander Langer, Christophe Paul, Felix Reidl,
Peter Rossmanith, Ignasi Sau, Somnath Sikdar,
Linear kernels and
singleexponential 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.
 Daniel Goncalves, E. J. Kim, On Exact Algorithms for
Permutation CSP
Theoretical Computer Science. 511, pp. 109116, 2013. arxiv
 E. J. Kim, Sebastian Ordyniak, ValuedBased Argumentation for
Treelike Value Graphs
Proceedings of the 4th International Conference on
Computational Models of Argument (COMMA 2012) pdf
 E. J. Kim, Christophe Paul, Geevarghese Philip, A
singleexponential FPT algorithm for K4minor 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. 186207, 2015.
 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 (AAAI12). arxiv
 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
 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. 402410, 2011.
arxiv
 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. 112125, 2012.
 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 (910),
pp. 17221736, 2011.
arxiv
 G. Gutin, E. J. Kim, M. Mnich, A. Yeo, Betweenness
Parameterized Above Tight Lower Bound,
Journal of Computer and System Sciences 76 (8), pp.
872878, 2010. arxiv
 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
 N. Alon, G. Gutin, E. J. Kim, S. Szeider, A. Yeo,
Solving Max
rSAT Above a Tight Lower Bound
conference version: the 21st Annual ACMSIAM
Symposium on Discrete Algorithms (SODA 2010).
journal version: Algorithmica 61 (3), pp. 638655, 2011. arxiv
 J. Daligault, G. Gutin, E. J. Kim, A. Yeo, FPT Algorithms and
Kernels for the Directed kLeaf Problem,
Journal of Computer and System Sciences 76 (2), pp.
144152, 2010. arxiv
 A. Gupta, G. Gutin, M. Karimi, E. J. Kim, A. Rafiey, Minimum
Cost Homomorphisms to Locally Semicomplete and Quasitransitive
Digraphs
Australasian Journal of Combinatorics 46, pp. 217232, 2010. arxiv
 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. 319330, 2010. arxiv
 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.
422429, 2011.
 N. Cohen, F. V. Fomin, G. Gutin, E. J. Kim, S. Saurabh, A.
Yeo, Algorithm for finding kvertex outtrees and its
application to kinternal outbranching 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. 650662, 2010.
 P. Dunkelmann, G. Gutin, E. J. Kim, On the Complexity of
Minimum Leaf Outbranching Problem,
Discrete Applied Mathematics 157 (13), pp. 30003004, 2009. arxiv
 G. Gutin, E. J. Kim, I. Razgon, Minimum Leaf Outbranching 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. 45714579, 2009. arxiv
 A. Gupta, M. Karimi, E. J. Kim, A. Rafiey, Minimum Cost
Homomorphisms to Locally Insemicomplete Digraphs,
Proceedings of the 2nd Annual International Conference on
Combinatorial Optimization and Applications (COCOA 2008).
pdf
 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.
 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.
2537, 2008. preprintpdf
Thesis
 PhD thesis: Parameterized Algorithms on Digraph and
Constraint Satisfaction Problems (pdf)
supervised by Gregory
Gutin
Last update: 29 March 2016
