1 Search Results for "Sun, Hao"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.25
Hitting Weighted Even Cycles in Planar Graphs

Authors: Alexander Göke, Jochen Koenemann, Matthias Mnich, and Hao Sun

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

Abstract
A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.
Cite as

Alexander Göke, Jochen Koenemann, Matthias Mnich, and Hao Sun. Hitting Weighted Even Cycles in Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{goke_et_al:LIPIcs.APPROX/RANDOM.2021.25,
  author =	{G\"{o}ke, Alexander and Koenemann, Jochen and Mnich, Matthias and Sun, Hao},
  title =	{{Hitting Weighted Even Cycles in Planar Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.25},
  URN =		{urn:nbn:de:0030-drops-147186},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.25},
  annote =	{Keywords: Even cycles, planar graphs, integrality gap}
}
  • Refine by Author
  • 1 Göke, Alexander
  • 1 Koenemann, Jochen
  • 1 Mnich, Matthias
  • 1 Sun, Hao

  • Refine by Classification
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 1 Even cycles
  • 1 integrality gap
  • 1 planar graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact