3 papers
cs.DM2026
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…
cs.CC2025
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. M…
cs.DS2025
A Constant-factor Approximation for Weighted Bond Cover
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos
The Weighted -Vertex Deletion for a class of graphs asks, weighted graph , for a minimum weight vertex set such that The case when…