Search Results

Documents authored by Ahn, Jungho

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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