Search Results

Documents authored by An, Shinwoo

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.6
Dynamic Parameterized Problems on Unit Disk Graphs

Authors: Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In this paper, we study fundamental parameterized problems such as k-Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk graphs. Given a vertex set V changing dynamically under vertex insertions and deletions, our goal is to maintain data structures so that the aforementioned parameterized problems on the unit disk graph induced by V can be solved efficiently. Although dynamic parameterized problems on general graphs have been studied extensively, no previous work focuses on unit disk graphs. In this paper, we present the first data structures for fundamental parameterized problems on dynamic unit disk graphs. More specifically, our data structure supports 2^O(√k) update time and O(k) query time for k-Path/Cycle. For the other problems, our data structures support O(log n) update time and 2^O(√k) query time, where k denotes the output size.
Cite as

Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song. Dynamic Parameterized Problems on Unit Disk Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2024.6,
  author =	{An, Shinwoo and Cho, Kyungjin and Jang, Leo and Jung, Byeonghyeon and Lee, Yudam and Oh, Eunjin and Shin, Donghun and Shin, Hyeonjun and Song, Chanho},
  title =	{{Dynamic Parameterized Problems on Unit Disk Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.6},
  URN =		{urn:nbn:de:0030-drops-221337},
  doi =		{10.4230/LIPIcs.ISAAC.2024.6},
  annote =	{Keywords: Unit disk graphs, dynamic parameterized algorithms, kernelization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.10
Sparse Outerstring Graphs Have Logarithmic Treewidth

Authors: Shinwoo An, Eunjin Oh, and Jie Xue

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with n vertices has treewidth O(αlog n), where α denotes the arboricity of the graph, with an almost matching lower bound of Ω(α log (n/α)). As a corollary, we show that a t-biclique-free outerstring graph has treewidth O(t(log t)log n). This leads to polynomial-time algorithms for most of the central NP-complete problems such as Independent Set, Vertex Cover, Dominating Set, Feedback Vertex Set, Coloring for sparse outerstring graphs. Also, we can obtain subexponential-time (exact, parameterized, and approximation) algorithms for various NP-complete problems such as Vertex Cover, Feedback Vertex Set and Cycle Packing for (not necessarily sparse) outerstring graphs.
Cite as

Shinwoo An, Eunjin Oh, and Jie Xue. Sparse Outerstring Graphs Have Logarithmic Treewidth. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ESA.2024.10,
  author =	{An, Shinwoo and Oh, Eunjin and Xue, Jie},
  title =	{{Sparse Outerstring Graphs Have Logarithmic Treewidth}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.10},
  URN =		{urn:nbn:de:0030-drops-210816},
  doi =		{10.4230/LIPIcs.ESA.2024.10},
  annote =	{Keywords: Outerstring graphs, geometric intersection graphs, treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.7
ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs

Authors: Shinwoo An and Eunjin Oh

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
In this paper, we consider the Cycle Packing problem on a unit disk graph defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set of k vertex-disjoint cycles of G if it exists. Our algorithm runs in time 2^O(√k) n^O(1). This improves the 2^O(√klog k) n^O(1)-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis.
Cite as

Shinwoo An and Eunjin Oh. ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.SoCG.2024.7,
  author =	{An, Shinwoo and Oh, Eunjin},
  title =	{{ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.7},
  URN =		{urn:nbn:de:0030-drops-199522},
  doi =		{10.4230/LIPIcs.SoCG.2024.7},
  annote =	{Keywords: Unit disk graphs, cycle packing, tree decomposition, parameterized algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.47
Feedback Vertex Set on Geometric Intersection Graphs

Authors: Shinwoo An and Eunjin Oh

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time 2^O(√k)(n+m), where n and m denote the numbers of vertices and edges, respectively. This improves the 2^O(√klog k) n^O(1)-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Also, our algorithm can be extended to handle geometric intersection graphs of similarly sized fat objects without increasing the running time.
Cite as

Shinwoo An and Eunjin Oh. Feedback Vertex Set on Geometric Intersection Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2021.47,
  author =	{An, Shinwoo and Oh, Eunjin},
  title =	{{Feedback Vertex Set on Geometric Intersection Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{47:1--47:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.47},
  URN =		{urn:nbn:de:0030-drops-154807},
  doi =		{10.4230/LIPIcs.ISAAC.2021.47},
  annote =	{Keywords: Feedback vertex set, intersection graphs, parameterized algorithm}
}
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