O-Joung Kwon

SODA Conference 2025 Conference Paper

A coarse Erdős-Pósa theorem

• Jungho Ahn
• Jochen Pascal Gollin
• Tony Huynh
• O-joung Kwon

AAAI Conference 2025 Conference Paper

Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs

• Shinwoo An
• Yeonsu Chang
• Kyungjin Cho
• O-Joung Kwon
• Myounghwan Lee
• Eunjin Oh
• Hyeonjun Shin

Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph G, to find a minimum set S of vertices in G such that there is a unique minimum vertex cover of G containing S. We show that PAU-VC is fixed parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in polynomial time on split graphs and unit interval graphs.

SODA Conference 2023 Conference Paper

A half-integral Erdős-Pósa theorem for directed odd cycles

• Ken-ichi Kawarabayashi
• Stephan Kreutzer
• O-joung Kwon
• Qiqin Xie

We prove that there exists a function f: ℕ → ℝ such that every directed graph G contains either k directed odd cycles where every vertex of G is contained in at most two of them, or a set of at most f ( k ) vertices meeting all directed odd cycles. We also give a polynomial-time algorithm for fixed k which outputs one of the two outcomes. Using this algorithmic result, we give a polynomial-time algorithm for fixed k to decide whether such k directed odd cycles exist, or there are no k vertex-disjoint directed odd cycles. This extends the half-integral Erdős-Pósa theorem for undirected odd cycles by Reed [Combinatorica 1999] to directed graphs.

SODA Conference 2022 Conference Paper

Directed Tangle Tree-Decompositions and Applications

• Archontia C. Giannopoulou
• Ken-ichi Kawarabayashi
• Stephan Kreutzer
• O-joung Kwon

The tangle tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs G that distinguishes all maximal directed tangles in G. Furthermore, for any integer k, we construct a directed tree-decomposition that distinguishes all directed tangles of order k. By relaxing the bound slightly, we can make the previous result algorithmic: for fixed k, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order 6 k –1 separated by some separation of order less than k. As a direct application of the tangle tree-decomposition theorem, we prove that for every fixed k there is a polynomial-time algorithm which, on input G, and source and sink vertices ( s 1, t 1 ), …, ( s k, t k ), either finds a family of paths P 1, …, P k such that each P i links s i to t i and every vertex of G is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting s i to t i. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result cannot be extended to fixed parameter tractability nor fully vertex-disjoint directed paths.

MFCS Conference 2020 Conference Paper

A Polynomial Kernel for 3-Leaf Power Deletion

• Jungho Ahn
• Eduard Eiben
• O-joung Kwon
• Sang-il Oum

For a non-negative integer 𝓁, a graph G is an 𝓁-leaf power of a tree T if V(G) is equal to the set of leaves of T, and distinct vertices v and w of G are adjacent if and only if the distance between v and w in T is at most 𝓁. Given a graph G, 3-Leaf Power Deletion asks whether there is a set S ⊆ V(G) of size at most k such that G\S is a 3-leaf power of some treeT. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance (G, k) to output an equivalent instance (G', k') such that k'≤ k and G' has at most O(k^14) vertices.

SODA Conference 2020 Conference Paper

The Directed Flat Wall Theorem

• Archontia C. Giannopoulou
• Ken-ichi Kawarabayashi
• Stephan Kreutzer
• O-joung Kwon

At the core of the Robertson-Seymour Theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. An important step towards this structure theorem is the Flat Wall Theorem [14], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.

MFCS Conference 2019 Conference Paper

Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

• Eduard Eiben
• Robert Ganian
• Thekla Hamm
• O-joung Kwon

We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i. e. , with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.

TCS Journal 2019 Journal Article

Mim-width III. Graph powers and generalized distance domination problems

• Lars Jaffke
• O-Joung Kwon
• Torstein J.F. Strømme
• Jan Arne Telle

We generalize the family of ( σ, ρ ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance- r Dominating Set and Distance- r Independent Set. We show that these distance problems are in XP parameterized by the structural parameter mim-width, and hence polynomial-time solvable on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. We obtain these results by showing that taking any power of a graph never increases its mim-width by more than a factor of two. To supplement these findings, we show that many classes of ( σ, ρ ) problems are W [ 1 ] -hard parameterized by mim-width + solution size. We show that powers of graphs of tree-width w − 1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1.

SODA Conference 2018 Conference Paper

Erdős-Pósa property of chordless cycles and its applications

• Eun Jung Kim 0002
• O-joung Kwon

A chordless cycle in a graph G is an induced subgraph of G which is a cycle of length at least four. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k + 1 vertex-disjoint chordless cycles, or ck 2 log k vertices hitting every chordless cycle for some constant c. It immediately implies an approximation algorithm of factor O (opt log opt) for C hordal V ertex D eletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ ≥ 5 do not have the Erdős-Pósa property. As a corollary, for a non-negative integral function w defined on the vertex set of a graph G, the minimum value Σ x ∊ S w ( x ) over all vertex sets S hitting all cycles of G is at most O ( k 2 log k ) where k is the maximum number of cycles (not necessarily vertex-disjoint) in G such that each vertex υ is used at most w ( υ ) times.

TCS Journal 2017 Journal Article

A width parameter useful for chordal and co-comparability graphs

• Dong Yeap Kang
• O-Joung Kwon
• Torstein J.F. Strømme
• Jan Arne Telle

Belmonte and Vatshelle (TCS 2013) used mim-width, a graph width parameter bounded on interval graphs and permutation graphs, to explain existing algorithms for many domination-type problems on those graph classes. We investigate new graph classes of bounded mim-width, strictly extending interval graphs and permutation graphs. The graphs K t ⊟ K t and K t ⊟ S t are graphs obtained from the disjoint union of two cliques of size t, and one clique of size t and one independent set of size t respectively, by adding a perfect matching. We prove that: • interval graphs are ( K 3 ⊟ S 3 ) -free chordal graphs; and ( K t ⊟ S t ) -free chordal graphs have mim-width at most t − 1, • permutation graphs are ( K 3 ⊟ K 3 ) -free co-comparability graphs; and ( K t ⊟ K t ) -free co-comparability graphs have mim-width at most t − 1, • chordal graphs and co-comparability graphs have unbounded mim-width in general. We obtain several algorithmic consequences; for instance, while Minimum Dominating Set is NP-complete on chordal graphs, it can be solved in time n O ( t ) on ( K t ⊟ S t ) -free chordal graphs. The third statement strengthens a result of Belmonte and Vatshelle stating that either those classes do not have constant mim-width or a decomposition with constant mim-width cannot be computed in polynomial time unless P = N P. We generalize these ideas to bigger graph classes. We introduce a new width parameter sim-width, of stronger modeling power than mim-width, by making a small change in the definition of mim-width. We prove that chordal graphs and co-comparability graphs have sim-width at most 1. We investigate a way to bound mim-width for graphs of bounded sim-width by excluding K t ⊟ K t and K t ⊟ S t as induced minors or induced subgraphs, and give algorithmic consequences. Lastly, we show that circle graphs have unbounded sim-width, and thus also unbounded mim-width.

MFCS Conference 2016 Conference Paper

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

• Eduard Eiben
• Robert Ganian
• O-joung Kwon

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis.