4 Search Results for "Kuinke, Philipp"

Document
DOI: 10.4230/LIPIcs.ESA.2025.55
Safe Sequences via Dominators in DAGs for Path-Covering Problems

Authors: Francisco Sena, Romeo Rizzi, and Alexandru I. Tomescu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A path-covering problem on a directed acyclic graph (DAG) requires finding a set of source-to-sink paths that cover all the nodes, all the arcs, or subsets thereof, and additionally they are optimal with respect to some function. In this paper we study safe sequences of nodes or arcs, namely sequences that appear in some path of every path cover of a DAG. We show that safe sequences admit a simple characterization via cutnodes. Moreover, we establish a connection between maximal safe sequences and leaf-to-root paths in the source- and sink-dominator trees of the DAG, which may be of independent interest in the extensive literature on dominators. With dominator trees, safe sequences admit an O(n)-size representation and a linear-time output-sensitive enumeration algorithm running in time O(m + o), where n and m are the number of nodes and arcs, respectively, and o is the total length of the maximal safe sequences. We then apply maximal safe sequences to simplify Integer Linear Programs (ILPs) for two path-covering problems, LeastSquares and MinPathError, which are at the core of RNA transcript assembly problems from bioinformatics. On various datasets, maximal safe sequences can be computed in under 0.1 seconds per graph, on average, and ILP solvers whose search space is reduced in this manner exhibit significant speed-ups. For example on graphs with a large width, average speed-ups are in the range 50-250× for MinPathError and in the range 80-350× for LeastSquares. Optimizing ILPs using safe sequences can thus become a fast building block of practical RNA transcript assembly tools, and more generally, of path-covering problems.
Cite as

Francisco Sena, Romeo Rizzi, and Alexandru I. Tomescu. Safe Sequences via Dominators in DAGs for Path-Covering Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sena_et_al:LIPIcs.ESA.2025.55,
  author =	{Sena, Francisco and Rizzi, Romeo and Tomescu, Alexandru I.},
  title =	{{Safe Sequences via Dominators in DAGs for Path-Covering Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.55},
  URN =		{urn:nbn:de:0030-drops-245230},
  doi =		{10.4230/LIPIcs.ESA.2025.55},
  annote =	{Keywords: directed acyclic graph, path cover, dominator tree, integer linear programming, least squares, minimum path error}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.40
First-Order Model-Checking in Random Graphs and Complex Networks

Authors: Jan Dreier, Philipp Kuinke, and Peter Rossmanith

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

Abstract
Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algorithms to solve problems on complex networks play a central role in today’s society. Algorithmic meta-theorems show that many problems can be solved efficiently. Since logic is a powerful tool to model problems, it has been used to obtain very general meta-theorems. In this work, we consider all problems definable in first-order logic and analyze which properties of complex networks allow them to be solved efficiently. The mathematical tool to describe complex networks are random graph models. We define a property of random graph models called α-power-law-boundedness. Roughly speaking, a random graph is α-power-law-bounded if it does not admit strong clustering and its degree sequence is bounded by a power-law distribution with exponent at least α (i.e. the fraction of vertices with degree k is roughly O(k^{-α})). We solve the first-order model-checking problem (parameterized by the length of the formula) in almost linear FPT time on random graph models satisfying this property with α ≥ 3. This means in particular that one can solve every problem expressible in first-order logic in almost linear expected time on these random graph models. This includes for example preferential attachment graphs, Chung-Lu graphs, configuration graphs, and sparse Erdős-Rényi graphs. Our results match known hardness results and generalize previous tractability results on this topic.
Cite as

Jan Dreier, Philipp Kuinke, and Peter Rossmanith. First-Order Model-Checking in Random Graphs and Complex Networks. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 40:1-40:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.ESA.2020.40,
  author =	{Dreier, Jan and Kuinke, Philipp and Rossmanith, Peter},
  title =	{{First-Order Model-Checking in Random Graphs and Complex Networks}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{40:1--40:23},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.40},
  URN =		{urn:nbn:de:0030-drops-129068},
  doi =		{10.4230/LIPIcs.ESA.2020.40},
  annote =	{Keywords: random graphs, average case analysis, first-order model-checking}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.14
Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size

Authors: Jan Dreier, Philipp Kuinke, and Peter Rossmanith

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

Abstract
Preferential attachment graphs are random graphs designed to mimic properties of real word networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We prove various structural asymptotic properties of this graph model. In particular, we show that the size of the largest r-shallow clique minor in Gⁿ_m is at most log(n)^{O(r²)}m^{O(r)}. Furthermore, there exists a one-subdivided clique of size log(n)^{1/4}. Therefore, preferential attachment graphs are asymptotically almost surely somewhere dense and algorithmic techniques developed for structurally sparse graph classes are not directly applicable. However, they are just barely somewhere dense. The removal of just slightly more than a polylogarithmic number of vertices asymptotically almost surely yields a graph with locally bounded treewidth.
Cite as

Jan Dreier, Philipp Kuinke, and Peter Rossmanith. Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.APPROX/RANDOM.2020.14,
  author =	{Dreier, Jan and Kuinke, Philipp and Rossmanith, Peter},
  title =	{{Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.14},
  URN =		{urn:nbn:de:0030-drops-126171},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.14},
  annote =	{Keywords: Random Graphs, Preferential Attachment, Sparsity, Somewhere Dense}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.10
The Complexity of Packing Edge-Disjoint Paths

Authors: Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We introduce and study the complexity of Path Packing. Given a graph G and a list of paths, the task is to embed the paths edge-disjoint in G. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case Exact Path Packing where the paths have to cover every edge in G exactly once is already NP-hard for two paths on 4-regular graphs.
Cite as

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.IPEC.2019.10,
  author =	{Dreier, Jan and Fuchs, Janosch and Hartmann, Tim A. and Kuinke, Philipp and Rossmanith, Peter and Tauer, Bjoern and Wang, Hung-Lung},
  title =	{{The Complexity of Packing Edge-Disjoint Paths}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.10},
  URN =		{urn:nbn:de:0030-drops-114710},
  doi =		{10.4230/LIPIcs.IPEC.2019.10},
  annote =	{Keywords: parameterized complexity, embedding, packing, covering, Hamiltonian path, unary binpacking, path-perfect graphs}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 2 2020
  • 1 2019

  • Refine by Author
  • 3 Dreier, Jan
  • 3 Kuinke, Philipp
  • 3 Rossmanith, Peter
  • 1 Fuchs, Janosch
  • 1 Hartmann, Tim A.
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Applied computing → Sequencing and genotyping technologies
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Integer programming

  • Refine by Keyword
  • 1 Hamiltonian path
  • 1 Preferential Attachment
  • 1 Random Graphs
  • 1 Somewhere Dense
  • 1 Sparsity
  • 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