Search Results

Documents authored by Ahn, Jungho

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.20
Approximating Maximum Cut on Interval Graphs and Split Graphs Beyond Goemans-Williamson

Authors: Jungho Ahn, Ian DeHaan, Eun Jung Kim, and Euiwoong Lee

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We present a polynomial-time (α_{GW} + ε)-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where α_{GW} ≈ 0.878 is the approximation guarantee of the Goemans-Williamson algorithm and ε > 10^{-34} is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant c > 0 such that there is no polyomial-time (1 - c)-approximation for Maximum Cut on split graphs.
Cite as

Jungho Ahn, Ian DeHaan, Eun Jung Kim, and Euiwoong Lee. Approximating Maximum Cut on Interval Graphs and Split Graphs Beyond Goemans-Williamson. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.APPROX/RANDOM.2025.20,
  author =	{Ahn, Jungho and DeHaan, Ian and Kim, Eun Jung and Lee, Euiwoong},
  title =	{{Approximating Maximum Cut on Interval Graphs and Split Graphs Beyond Goemans-Williamson}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{20:1--20:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.20},
  URN =		{urn:nbn:de:0030-drops-243869},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.20},
  annote =	{Keywords: Maximum cut, graph theory, interval graphs, split graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.6
Twin-Width One

Authors: Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We investigate the structure of graphs of twin-width at most 1, and obtain the following results: - Graphs of twin-width at most 1 are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a 1-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a 1-contraction sequence of a graph, or guarantees that it has twin-width more than 1. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs.
Cite as

Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht. Twin-Width One. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.STACS.2025.6,
  author =	{Ahn, Jungho and Jacob, Hugo and K\"{o}hler, Noleen and Paul, Christophe and Reinald, Amadeus and Wiederrecht, Sebastian},
  title =	{{Twin-Width One}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.6},
  URN =		{urn:nbn:de:0030-drops-228319},
  doi =		{10.4230/LIPIcs.STACS.2025.6},
  annote =	{Keywords: Twin-width, Hereditary graph classes, Intersection model}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.5
Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes

Authors: Jungho Ahn, Jinha Kim, and O-joung Kwon

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Let ℱ be a family of graphs, and let p,r be nonnegative integers. For a graph G and an integer k, the (p,r,ℱ)-Covering problem asks whether there is a set D ⊆ V(G) of size at most k such that if the p-th power of G has an induced subgraph isomorphic to a graph in ℱ, then it is at distance at most r from D. The (p,r,ℱ)-Packing problem asks whether G^p has k induced subgraphs H₁,…,H_k such that each H_i is isomorphic to a graph in ℱ, and for i,j ∈ {1,…,k}, the distance between V(H_i) and V(H_j) in G is larger than r. We show that for every fixed nonnegative integers p,r and every fixed nonempty finite family ℱ of connected graphs, (p,r,ℱ)-Covering with p ≤ 2r+1 and (p,r,ℱ)-Packing with p ≤ 2⌊r/2⌋+1 admit almost linear kernels on every nowhere dense class of graphs, parameterized by the solution size k. As corollaries, we prove that Distance-r Vertex Cover, Distance-r Matching, ℱ-Free Vertex Deletion, and Induced-ℱ-Packing for any fixed finite family ℱ of connected graphs admit almost linear kernels on every nowhere dense class of graphs. Our results extend the results for Distance-r Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and for Distance-r Independent Set by Pilipczuk and Siebertz (EJC 2021).
Cite as

Jungho Ahn, Jinha Kim, and O-joung Kwon. Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2023.5,
  author =	{Ahn, Jungho and Kim, Jinha and Kwon, O-joung},
  title =	{{Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.5},
  URN =		{urn:nbn:de:0030-drops-193072},
  doi =		{10.4230/LIPIcs.ISAAC.2023.5},
  annote =	{Keywords: kernelization, independent set, dominating set, covering, packing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.62
Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion

Authors: Jungho Ahn, Eun Jung Kim, and Euiwoong Lee

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which the input is a vertex weighted graph G = (V, E) and the goal is to delete S ⊆ V with minimum weight such that G⧵S ∈ ℱ. Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when ℱ is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest.
Cite as

Jungho Ahn, Eun Jung Kim, and Euiwoong Lee. Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2020.62,
  author =	{Ahn, Jungho and Kim, Eun Jung and Lee, Euiwoong},
  title =	{{Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.62},
  URN =		{urn:nbn:de:0030-drops-134063},
  doi =		{10.4230/LIPIcs.ISAAC.2020.62},
  annote =	{Keywords: ptolemaic, approximation algorithm, linear programming, feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.5
A Polynomial Kernel for 3-Leaf Power Deletion

Authors: Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
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.
Cite as

Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum. A Polynomial Kernel for 3-Leaf Power Deletion. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.MFCS.2020.5,
  author =	{Ahn, Jungho and Eiben, Eduard and Kwon, O-joung and Oum, Sang-il},
  title =	{{A Polynomial Kernel for 3-Leaf Power Deletion}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.5},
  URN =		{urn:nbn:de:0030-drops-126763},
  doi =		{10.4230/LIPIcs.MFCS.2020.5},
  annote =	{Keywords: 𝓁-leaf power, parameterized algorithms, kernelization}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact