38 citations · 189 across the 43 of their papers we have counts for
56 papers
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
On weighted graph separation problems and flow-augmentation
Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk +2
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \te…
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula over a fixed, finite Boolean constraint language , with or without weights. Mo…
Algorithmic Applications of Tree-Cut Width
Robert Ganian, Eun Jung Kim, Stefan Szeider
The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper,…
Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3
We introduce the notion of delineation. A graph class is said delineated if for every hereditary closure of a subclass of , it holds that $\ma…
Twin-width VI: the lens of contraction sequences
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +1
A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on…