Search Results

Documents authored by Hauser, Fanny

Artifact
Software
DOI: 10.4230/artifacts.22579
Arcee

Authors: Kimon Boehmer, Lukas Lee George, Fanny Hauser, and Jesse Palarus

Abstract
Cite as

Kimon Boehmer, Lukas Lee George, Fanny Hauser, Jesse Palarus. Arcee (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{Arcee,
   title = {{Arcee}}, 
   author = {Boehmer, Kimon and George, Lukas Lee and Hauser, Fanny and Palarus, Jesse},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:4a1810b816bec954e0780d591b0c79276ac8f285;origin=https://github.com/lucidLuckylee/pace_2024;visit=swh:1:snp:c15056f72ef6b62e3ef8f87b844229391c3a10b8;anchor=swh:1:rev:9269201822ced0770c31bfc3fccb48c45abbfb42}{\texttt{swh:1:dir:4a1810b816bec954e0780d591b0c79276ac8f285}} (visited on 2024-12-05)},
   url = {https://github.com/lucidLuckylee/pace_2024},
   doi = {10.4230/artifacts.22579},
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.14
The Parameterized Complexity Landscape of Two-Sets Cut-Uncut

Authors: Matthias Bentert, Fedor V. Fomin, Fanny Hauser, and Saket Saurabh

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
In Two-Sets Cut-Uncut, we are given an undirected graph G = (V,E) and two terminal sets S and T. The task is to find a minimum cut C in G (if there is any) separating S from T under the following "uncut" condition. In the graph (V,E⧵C), the terminals in each terminal set remain in the same connected component. In spite of the superficial similarity to the classic problem Minimum s-t-Cut, Two-Sets Cut-Uncut is computationally challenging. In particular, even deciding whether such a cut of any size exists, is already NP-complete. We initiate a systematic study of Two-Sets Cut-Uncut within the context of parameterized complexity. By leveraging known relations between many well-studied graph parameters, we characterize the structural properties of input graphs that allow for polynomial kernels, fixed-parameter tractability (FPT), and slicewise polynomial algorithms (XP). Our main contribution is the near-complete establishment of the complexity of these algorithmic properties within the described hierarchy of graph parameters. On a technical level, our main results are fixed-parameter tractability for the (vertex-deletion) distance to cographs and an OR-cross composition excluding polynomial kernels for the vertex cover number of the input graph (under the standard complexity assumption NP ̸ ⊆ coNP/poly).
Cite as

Matthias Bentert, Fedor V. Fomin, Fanny Hauser, and Saket Saurabh. The Parameterized Complexity Landscape of Two-Sets Cut-Uncut. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.IPEC.2024.14,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Hauser, Fanny and Saurabh, Saket},
  title =	{{The Parameterized Complexity Landscape of Two-Sets Cut-Uncut}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{14:1--14:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.14},
  URN =		{urn:nbn:de:0030-drops-222400},
  doi =		{10.4230/LIPIcs.IPEC.2024.14},
  annote =	{Keywords: Fixed-parameter tractability, Polynomial Kernels, W\lbrack1\rbrack-hardness, XP, para-NP-Hardness}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.33
PACE Solver Description: Arcee

Authors: Kimon Boehmer, Lukas Lee George, Fanny Hauser, and Jesse Palarus

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
The 2024 PACE Challenge focused on the One-Sided Crossing Minimization (OCM) problem, which aims to minimize edge crossings in a bipartite graph with a fixed order in one partition and a free order in the other. We describe our OCM solver submission that utilizes various reduction rules for OCM and, for the heuristic track, employs local search approaches as well as techniques to escape local minima. The exact solver uses an ILP formulation and branch & bound to solve an equivalent Feedback Arc Set instance.
Cite as

Kimon Boehmer, Lukas Lee George, Fanny Hauser, and Jesse Palarus. PACE Solver Description: Arcee. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 33:1-33:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boehmer_et_al:LIPIcs.IPEC.2024.33,
  author =	{Boehmer, Kimon and George, Lukas Lee and Hauser, Fanny and Palarus, Jesse},
  title =	{{PACE Solver Description: Arcee}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{33:1--33:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.33},
  URN =		{urn:nbn:de:0030-drops-222595},
  doi =		{10.4230/LIPIcs.IPEC.2024.33},
  annote =	{Keywords: PACE 2024, One-Sided Crossing Minimization, OCM}
}
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