2 Search Results for "Vågset, Erlend Raa"


Document
ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth

Authors: Mitchell Black, Nello Blaser, Amir Nayyeri, and Erlend Raa Vågset

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Given a simplicial complex with n simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth k of the Hasse diagram that run in 2^{O(k log k)}n^{O(1)} time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.

Cite as

Mitchell Black, Nello Blaser, Amir Nayyeri, and Erlend Raa Vågset. ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.SoCG.2022.17,
  author =	{Black, Mitchell and Blaser, Nello and Nayyeri, Amir and V\r{a}gset, Erlend Raa},
  title =	{{ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.17},
  URN =		{urn:nbn:de:0030-drops-160253},
  doi =		{10.4230/LIPIcs.SoCG.2022.17},
  annote =	{Keywords: Computational Geometry, Surface Recognition, Treewidth, Hasse Diagram, Simplicial Complexes, Low-Dimensional Topology, Parameterized Complexity, Computational Complexity}
}
Document
Kernelization of Whitney Switches

Authors: Fedor V. Fomin and Petr A. Golovach

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney’s theorem: Given 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size 𝒪(k), and thus, is fixed-parameter tractable when parameterized by k.

Cite as

Fedor V. Fomin and Petr A. Golovach. Kernelization of Whitney Switches. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ESA.2020.48,
  author =	{Fomin, Fedor V. and Golovach, Petr A.},
  title =	{{Kernelization of Whitney Switches}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{48:1--48:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.48},
  URN =		{urn:nbn:de:0030-drops-129144},
  doi =		{10.4230/LIPIcs.ESA.2020.48},
  annote =	{Keywords: Whitney switch, 2-isomorphism, Parameterized Complexity, kernelization}
}
  • Refine by Author
  • 1 Black, Mitchell
  • 1 Blaser, Nello
  • 1 Fomin, Fedor V.
  • 1 Golovach, Petr A.
  • 1 Nayyeri, Amir
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Algebraic topology
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 Parameterized Complexity
  • 1 2-isomorphism
  • 1 Computational Complexity
  • 1 Computational Geometry
  • 1 Hasse Diagram
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

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