12 Search Results for "Stege, Ulrike"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.6
A Dimension-Reducing Fréchet Simplification Oracle

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n).
Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. A Dimension-Reducing Fréchet Simplification Oracle. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2025.6,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{A Dimension-Reducing Fr\'{e}chet Simplification Oracle}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.6},
  URN =		{urn:nbn:de:0030-drops-249149},
  doi =		{10.4230/LIPIcs.ISAAC.2025.6},
  annote =	{Keywords: Computational geometry, discrete Fr\'{e}chet distance, curve simplification oracle, restricted minimum enclosing disk queries}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.13
Solving Partial Dominating Set and Related Problems Using Twin-Width

Authors: Jakub Balabán, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d,k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.
Cite as

Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving Partial Dominating Set and Related Problems Using Twin-Width. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.13,
  author =	{Balab\'{a}n, Jakub and Mock, Daniel and Rossmanith, Peter},
  title =	{{Solving Partial Dominating Set and Related Problems Using Twin-Width}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.13},
  URN =		{urn:nbn:de:0030-drops-241203},
  doi =		{10.4230/LIPIcs.MFCS.2025.13},
  annote =	{Keywords: Partial Dominating Set, Partial Vertex Cover, meta-algorithm, counting logic, twin-width}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.19
Designing Output Sensitive Algorithms for Subgraph Enumeration

Authors: Alessio Conte, Kazuhiro Kurita, Andrea Marino, Giulia Punzi, Takeaki Uno, and Kunihiro Wasa

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
The enumeration of all subgraphs respecting some structural property is a fundamental task in theoretical computer science, with practical applications in many branches of data mining and network analysis. It is often of interest to only consider solutions (subgraphs) that are maximal under inclusion, and to achieve output-sensitive complexity, i.e., bounding the running time with respect to the number of subgraphs produced. In this paper, we provide a survey of techniques for designing output-sensitive algorithms for subgraph enumeration, including partition-based approaches such as flashlight search, solution-graph traversal methods such as reverse search, and cost amortization strategies such as push-out amortization. We also briefly discuss classes of efficiency, hardness of enumeration, and variants such as approximate enumeration. The paper is meant as an accessible handbook for learning the basics of the field and as a practical reference for selecting state-of-the-art subgraph enumeration strategies fitting to one’s needs.
Cite as

Alessio Conte, Kazuhiro Kurita, Andrea Marino, Giulia Punzi, Takeaki Uno, and Kunihiro Wasa. Designing Output Sensitive Algorithms for Subgraph Enumeration. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 19:1-19:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{conte_et_al:OASIcs.Grossi.19,
  author =	{Conte, Alessio and Kurita, Kazuhiro and Marino, Andrea and Punzi, Giulia and Uno, Takeaki and Wasa, Kunihiro},
  title =	{{Designing Output Sensitive Algorithms for Subgraph Enumeration}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{19:1--19:40},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.19},
  URN =		{urn:nbn:de:0030-drops-238180},
  doi =		{10.4230/OASIcs.Grossi.19},
  annote =	{Keywords: Graph algorithms, Graph enumeration, Output sensitive enumeration}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.51
Parameterized Geometric Graph Modification with Disk Scaling

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph G and an integer k ∈ ℕ as input, the goal is to determine whether we can perform at most k operations on G to transform it into a graph belonging to a specified graph class ℱ. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Parameterized Geometric Graph Modification with Disk Scaling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ITCS.2025.51,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Parameterized Geometric Graph Modification with Disk Scaling}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.51},
  URN =		{urn:nbn:de:0030-drops-226795},
  doi =		{10.4230/LIPIcs.ITCS.2025.51},
  annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
Document
DOI: 10.4230/DagSemProc.09142.1
09142 Manifesto – Perspectives Workshop: Preventing the Brainware Crisis

Authors: Stephan Diehl and Ulrike Stege

Published in: Dagstuhl Seminar Proceedings, Volume 9142, Perspectives Workshop: Preventing the Brainware Crisis (2011)

Abstract
This manifesto summarizes the outcomes of the Dagstuhl Perspectives Workshop "Preventing the Brainware Crisis" held in Spring 2009. Our acquired goals are summarized by the following recommendations: to make computer science/computing science/informatics programs more attractive to women, to make curricula more engaging and interdisciplinary, and to make the public more aware of computer scientists’ work. We address specific audiences with particular recommendations and feature 10 tips on how to publicize computer science via the media.
Cite as

Stephan Diehl and Ulrike Stege. 09142 Manifesto – Perspectives Workshop: Preventing the Brainware Crisis. In Perspectives Workshop: Preventing the Brainware Crisis. Dagstuhl Seminar Proceedings, Volume 9142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{diehl_et_al:DagSemProc.09142.1,
  author =	{Diehl, Stephan and Stege, Ulrike},
  title =	{{09142 Manifesto – Perspectives Workshop: Preventing the Brainware Crisis}},
  booktitle =	{Perspectives Workshop: Preventing the Brainware Crisis},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{9142},
  editor =	{Stephan Diehl and Michael R. Fellows and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09142.1},
  URN =		{urn:nbn:de:0030-drops-31434},
  doi =		{10.4230/DagSemProc.09142.1},
  annote =	{Keywords: Computer science education, outreach, people networking, enrolment crisis, schools}
}
Document
DOI: 10.4230/DagSemProc.07281.2
07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs

Authors: Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
The following is a list of the problems presented on Monday, July 9, 2007 at the open-problem session of the Seminar on Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, held at Schloss Dagstuhl in Wadern, Germany.
Cite as

Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:DagSemProc.07281.2,
  author =	{Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike},
  title =	{{07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.2},
  URN =		{urn:nbn:de:0030-drops-12542},
  doi =		{10.4230/DagSemProc.07281.2},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.07281.1
07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs

Authors: Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
From 8th to 13th July 2007, the Dagstuhl Seminar ``Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:DagSemProc.07281.1,
  author =	{Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike},
  title =	{{07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.1},
  URN =		{urn:nbn:de:0030-drops-12450},
  doi =		{10.4230/DagSemProc.07281.1},
  annote =	{Keywords: Parameterized complexity, fixed-parameter tractability, graph structure theory}
}
Document
DOI: 10.4230/DagSemProc.07281.3
Approximating Solution Structure

Authors: Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
hen it is hard to compute an optimal solution $y in optsol(x)$ to an instance $x$ of a problem, one may be willing to settle for an efficient algorithm $A$ that computes an approximate solution $A(x)$. The most popular type of approximation algorithm in Computer Science (and indeed many other applications) computes solutions whose value is within some multiplicative factor of the optimal solution value, {em e.g.}, $max(frac{val(A(x))}{optval(x)}, frac{optval(x)}{val(A(x))}) leq h(|x|)$ for some function $h()$. However, an algorithm might also produce a solution whose structure is ``close'' to the structure of an optimal solution relative to a specified solution-distance function $d$, {em i.e.}, $d(A(x), y) leq h(|x|)$ for some $y in optsol(x)$. Such structure-approximation algorithms have applications within Cognitive Science and other areas. Though there is an extensive literature dating back over 30 years on value-approximation, there is to our knowledge no work on general techniques for assessing the structure-(in)approximability of a given problem. In this talk, we describe a framework for investigating the polynomial-time and fixed-parameter structure-(in)approximability of combinatorial optimization problems relative to metric solution-distance functions, {em e.g.}, Hamming distance. We motivate this framework by (1) describing a particular application within Cognitive Science and (2) showing that value-approximability does not necessarily imply structure-approximability (and vice versa). This framework includes definitions of several types of structure approximation algorithms analogous to those studied in value-approximation, as well as structure-approximation problem classes and a structure-approximability-preserving reducibility. We describe a set of techniques for proving the degree of structure-(in)approximability of a given problem, and summarize all known results derived using these techniques. We also list 11 open questions summarizing particularly promising directions for future research within this framework. vspace*{0.15in} oindent (co-presented with Todd Wareham) vspace*{0.15in} jointwork{Hamilton, Matthew; M"{u}ller, Moritz; van Rooij, Iris; Wareham, Todd}
Cite as

Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham. Approximating Solution Structure. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vanrooij_et_al:DagSemProc.07281.3,
  author =	{van Rooij, Iris and Hamilton, Matthew and M\"{u}ller, Moritz and Wareham, Todd},
  title =	{{Approximating Solution Structure}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.3},
  URN =		{urn:nbn:de:0030-drops-12345},
  doi =		{10.4230/DagSemProc.07281.3},
  annote =	{Keywords: Approximation Algorithms, Solution Structure}
}
Document
DOI: 10.4230/DagSemProc.07281.4
Directed Feedback Vertex Set is Fixed-Parameter Tractable

Authors: Igor Razgon and Barry O'Sullivan

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose an algorithm which solves this problem in $O(8^kk!*poly(n))$.
Cite as

Igor Razgon and Barry O'Sullivan. Directed Feedback Vertex Set is Fixed-Parameter Tractable. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{razgon_et_al:DagSemProc.07281.4,
  author =	{Razgon, Igor and O'Sullivan, Barry},
  title =	{{Directed Feedback Vertex Set is Fixed-Parameter Tractable}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.4},
  URN =		{urn:nbn:de:0030-drops-12363},
  doi =		{10.4230/DagSemProc.07281.4},
  annote =	{Keywords: Directed FVS, Multicut, Directed Acyclic Graph (DAG)}
}
Document
DOI: 10.4230/DagSemProc.07281.5
Directed Feedback Vertex Set Problem is FPT

Authors: Jianer Chen, Yang Liu, and Songiian Lu

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
To decide if the {sc parameterized feedback vertex set} problem in directed graph is fixed-parameter tractable is a long standing open problem. In this paper, we prove that the {sc parameterized feedback vertex set} in directed graph is fixed-parameter tractable and give the first FPT algorithm of running time $O((1.48k)^kn^{O(1)})$ for it. As the {sc feedback arc set} problem in directed graph can be transformed to a {sc feedback vertex set} problem in directed graph, hence we also show that the {sc parameterized feedback arc set} problem can be solved in time of $O((1.48k)^kn^{O(1)})$.
Cite as

Jianer Chen, Yang Liu, and Songiian Lu. Directed Feedback Vertex Set Problem is FPT. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.07281.5,
  author =	{Chen, Jianer and Liu, Yang and Lu, Songiian},
  title =	{{Directed Feedback Vertex Set Problem is FPT}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.5},
  URN =		{urn:nbn:de:0030-drops-12333},
  doi =		{10.4230/DagSemProc.07281.5},
  annote =	{Keywords: Directed feedback vertex set problem, parameterized algorithm,}
}
Document
DOI: 10.4230/DagSemProc.07281.6
Exact Elimination of Cycles in Graphs

Authors: Daniel Raible and Henning Fernau

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
One of the standard basic steps in drawing hierarchical graphs is to invert some arcs of the given graph to make the graph acyclic. We discuss exact and parameterized algorithms for this problem. In particular we examine a graph class called $(1,n)$-graphs, which contains cubic graphs. For both exact and parameterized algorithms we use a non-standard measure approach for the analysis. The analysis of the parameterized algorithm is of special interest, as it is not an amortized analysis modelled by 'finite states' but rather a 'top-down' amortized analysis. For $(1,n)$-graphs we achieve a running time of $Oh^*(1.1871^m)$ and $Oh^*(1.212^k)$, for cubic graphs $Oh^*(1.1798^m)$ and $Oh^*(1.201^k)$, respectively. As a by-product the trivial bound of $2^n$ for {sc Feedback Vertex Set} on planar directed graphs is broken.
Cite as

Daniel Raible and Henning Fernau. Exact Elimination of Cycles in Graphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{raible_et_al:DagSemProc.07281.6,
  author =	{Raible, Daniel and Fernau, Henning},
  title =	{{Exact Elimination of Cycles in Graphs}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.6},
  URN =		{urn:nbn:de:0030-drops-12353},
  doi =		{10.4230/DagSemProc.07281.6},
  annote =	{Keywords: Maximum Acyclic Subgraph, Feedback Arc Set, Amortized Analysis, Exact exponential algorthms}
}
  • Refine by Type
  • 12 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2011
  • 6 2007

  • Refine by Author
  • 3 Stege, Ulrike
  • 2 Demaine, Erik
  • 2 Gutin, Gregory Z.
  • 2 Marx, Daniel
  • 1 Aronov, Boris
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 OASIcs
  • 7 DagSemProc

  • Refine by Classification
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph enumeration
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Algorithm Engineering
  • 1 Amortized Analysis
  • 1 Approximation Algorithms
  • 1 Computational geometry
  • 1 Computer science education
  • Show More...

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