Search Results

Documents authored by Noguchi, Takashi

Document
DOI: 10.4230/LIPIcs.ESA.2026.93
An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers

Authors: Yusuke Kobayashi and Takashi Noguchi

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph G, and the objective is to find a 2-vertex-connected spanning subgraph S of G with the minimum number of edges. In the context of survivable network design, 2-VCSS is one of the most fundamental and well-studied problems. There has been active research on improving the approximation ratio of algorithms, and the current best ratio is 4/3, achieved by Bosch-Calvo, Grandoni, and Jabal Ameli. In this paper, we improve the approximation ratio to 95/72+ε (< 1.32). The key idea in our algorithm is to introduce a 2-edge-cover without certain cycle components, and use it as an initial solution.
Cite as

Yusuke Kobayashi and Takashi Noguchi. An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 93:1-93:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ESA.2026.93,
  author =	{Kobayashi, Yusuke and Noguchi, Takashi},
  title =	{{An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{93:1--93:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.93},
  URN =		{urn:nbn:de:0030-drops-272293},
  doi =		{10.4230/LIPIcs.ESA.2026.93},
  annote =	{Keywords: approximation algorithm, survivable network design, minimum 2-vertex-connected spanning subgraph, triangle-free 2-matching}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.49
An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover

Authors: Yusuke Kobayashi and Takashi Noguchi

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

Abstract
The 2-Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the most fundamental and well-studied problems in the context of network design. We are given an undirected graph G, and the objective is to find a 2-edge-connected spanning subgraph H of G with the minimum number of edges. For this problem, a lot of approximation algorithms have been proposed in the literature. In particular, very recently, Garg, Grandoni, and Ameli gave an approximation algorithm for 2-ECSS with a factor of 1.326, which is the best approximation ratio. In this paper, under the assumption that a maximum triangle-free 2-matching can be found in polynomial time in a graph, we give a (1.3+ε)-approximation algorithm for 2-ECSS, where ε is an arbitrarily small positive fixed constant. Note that a complicated polynomial-time algorithm for finding a maximum triangle-free 2-matching is announced by Hartvigsen in his PhD thesis, but it has not been peer-reviewed or checked in any other way. In our algorithm, we compute a minimum triangle-free 2-edge-cover in G with the aid of the algorithm for finding a maximum triangle-free 2-matching. Then, with the obtained triangle-free 2-edge-cover, we apply the arguments by Garg, Grandoni, and Ameli.
Cite as

Yusuke Kobayashi and Takashi Noguchi. An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2023.49,
  author =	{Kobayashi, Yusuke and Noguchi, Takashi},
  title =	{{An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{49:1--49:10},
  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.49},
  URN =		{urn:nbn:de:0030-drops-193514},
  doi =		{10.4230/LIPIcs.ISAAC.2023.49},
  annote =	{Keywords: approximation algorithm, survivable network design, minimum 2-edge-connected spanning subgraph, triangle-free 2-matching}
}

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact