Forschungsseminar
Wintersemester 2024
(AAAI Poster Session): Something with Embeddings
- Datum: Mi, 12 Feb 2025, 14:00
- Ort: SR 301
- Vortragende(r): Jean-Pierre von der Heydt
- Inhalt: Exact date still unclear
Rerouting Curves on Surfaces
- Datum: Mi, 22 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Torsten Ueckerdt
Interactive Theorem Proving
- Datum: Mi, 15 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Markus Himmel
- Inhalt: Proof assistants are software tools for building and maintaining digital libraries of mathematical theorems and their proofs. Computer scientists have been working on (and with) these tools since the 1960s, but it took until the 2020s for them to gain traction with a general mathematical audience. I will give a demonstration of a proof assistant called Lean and present an overview over recent successes of proof assistants in mainstream mathematics and future opportunities afforded by a comprehensive library of digitized mathematical proofs.
Small Separators in Road Networks
- Datum: Fr, 10 Jan 2025, 14:15
- Ort: SR 301
- Vortragende(r): Samuel Born, Masterarbeit Kurzvortrag
Lineplanning
- Datum: Fr, 10 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Maximilian Walz, Masterarbeit Kurzvortrag
Crossing Number of 2-Planar Graphs
- Datum: Mi, 8 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Miriam Goetze
- Inhalt: We consider 2-planar drawings, that is drawings of graphs where every edge is crossed at most 2 times. Our aim is to bound the number of crossings in terms of the number of vertices. In order to obtain such a bound, we make use of the density formula, a novel tool introduced recently (Kaufmann et al. 2024). The density formula relates the number of vertices, crossings and edges in a drawing. We present the density formula and show how to apply it to the crossing number of 2-planar graphs. This is joint work with Michael Hoffmann, Ignaz Rutter and Torsten Ueckerdt.
Pattern Dominating Set in Sparse Graphs
- Datum: Mi, 18 Dez 2024, 14:30
- Ort: SR 301
- Vortragende(r): Jonathan Dransfeld, PDF Intermediate Presentation
Practice Talk [Completeness Theorems for k-SUM and Geometric Friends (Deciding Integer Linear Arithmetic Fragments)]
- Datum: Mi, 18 Dez 2024, 14:00
- Ort: SR 301
- Vortragende(r): Geri Gokaj
- Inhalt: Note: The talk will be similar to the work in progress talk given in September. It will be a bit more polished and I will show some more proofs, which connect logic and geometry. We study the k-SUM problem from a descriptive complexity theory perspective to determine its power. We introduce a class of problems FOP_Z, which roughly corresponds to linear integer arithmetic over finite subsets and show that k-SUM is complete for the existential fragment of FOP_Z. Furthermore, we study different quantifier structures problems of FOP_Z, and show connections to known geometric problems such as the Hausdorff Distance under Translation and the Pareto Sum. Joint Work with Marvin Künnemann.
Fine-Grained Complexity of Sparse CSP
- Datum: Fr, 13 Dez 2024, 14:45
- Ort: SR 301
- Vortragende(r): Timo Fritsch, (MA Kurzvortrag)
Heuristics for FLaMECaST
- Datum: Fr, 13 Dez 2024, 14:30
- Ort: SR 301
- Vortragende(r): Simon Kienle, BA Kurzvortrag
Power Domination with Bounded Propagation
- Datum: Fr, 13 Dez 2024, 14:15
- Ort: SR 301
- Vortragende(r): Christoph Niederbudde, BA Kurzvortrag
CCH with edge insertion
- Datum: Fr, 13 Dez 2024, 14:00
- Ort: SR 301
- Vortragende(r): Benedikt Müller, Kurzvortrag Bachelorarbeit
Erdö-Posa property of cycles that are far apart
- Datum: Mi, 11 Dez 2024, 14:30
- Ort: SR 301
- Vortragende(r): Piotr Micek, Jagiellonian University Krakow
- Inhalt: We prove that there exist functions f and g such that for all nonnegative integers k and d, for every graph G, either G contains k cycles such that vertices of different cycles have distance greater than d in G, or there exists a subset X of vertices of G with |X| <= f(k) such that G-B_G(X,g(d)) is a forest, where B_G(X,r) denotes the set of vertices of G having distance at most r from a vertex of X. Joint work with Vida Dujmovic, Gwenael Joret, and Pat Morin.
Cops and Attacking Robber
- Datum: Fr, 6 Dez 2024, 14:00
- Ort: SR 301
- Vortragende(r): Florian Brendle, Bsc-Kurzvortrag - Ueckerdt
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D
- Datum: Mi, 4 Dez 2024, 14:00
- Ort: SR 301
- Vortragende(r): Marvin Künnemann
Broadcast, Reduction and beyond with Block Schedules and Circulant Graphs
- Datum: Di, 3 Dez 2024, 11:30
- Ort: SR 301
- Vortragende(r): Jesper Träff, TU Vienna
- Inhalt: We present a round-optimal broadcast algorithm for broadcasting $n$ blocks of data to $p$ processors communicating in a regular, logarithmic degree circulant graph pattern. This immediately leads to likewise round-optimal algorithms for the reduction to root, all-to-all broadcast (allgatherv) and reduce-scatter (block-reduce) operations. The algorithm relies on block schedules with certain properties which we indicate can be computed optimally in $O(log p)$ operations per processor without communication. The communication pattern and algorithms are attractive for implementing most of the standard, dense collective operations of MPI.
Some really fancy topic
- Datum: Mi, 27 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Wendy Yi
Degree Independent Weights for Weighted Graph Embeddings
- Datum: Fr, 22 Nov 2024, 14:45
- Ort: SR 301
- Vortragende(r): Karl Bernhard, BA Kurzvortrag
Algorithms for k-Power Dominating Set
- Datum: Fr, 22 Nov 2024, 14:15
- Ort: SR 301
- Vortragende(r): Tobias Hoch, BA Abschlussvortrag
- Inhalt: The Power Dominating Set (PDS) problem is a graph covering problem with significant applications in energy informatics. The goal is to identify the smallest subset S subseteq V such that every vertex in the graph is monitored according to specific rules. In this paper, we extend the traditional PDS problem by introducing the k-Power Dominating Set (k-PDS), a generalized variant that considers an additional parameter k. We begin by examining existing reduction rules for PDS, adapting them to the k-PDS context where applicable, and deriving new reduction rules unique to this variant. Additionally, we propose an efficient algorithm that solves both PDS and k-PDS on cactus graphs with linear time complexity.
Single-Transfer Journeys in Dynamic Taxi Sharing with Meeting Points
- Datum: Fr, 22 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Johannes Breitling, Kurzvortrag Bachelorarbeit
Conditionally Tight Algorithms for Maximum $k$-Coverage and Partial $k$-Dominating Set via Arity-Reducing Hypercuts
- Datum: Mi, 20 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Mirza Redzic
Combining Vertex Orderings
- Datum: Fr, 15 Nov 2024, 14:45
- Ort: SR 301
- Vortragende(r): Moritz Bär, Kurzvortrag Msc - Ueckerdt
Algorithmic Aspects of Product Structure
- Datum: Fr, 15 Nov 2024, 14:30
- Ort: SR 301
- Vortragende(r): Antonia Heiming, Kurzvortrag Bachelorarbeit
Complexity of Solo Chess Variants
- Datum: Fr, 15 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Kolja Kühn, MA
Structure and Independence in Hyperbolic Uniform Disk Graphs
- Datum: Mi, 13 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Thomas Bläsius
- Inhalt: We consider intersection graphs of disks of radius r in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of r, where very small r corresponds to an almost-Euclidean setting and $r in Omega(log n)$ corresponds to a firmly hyperbolic setting. We observe that larger values of r create simpler graph classes, at least in terms of separators and the computational complexity of the Independent Set problem.
Fold And Cut
- Datum: Fr, 8 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Sven Geißler, PdF Final Presentation, Scale
- Inhalt: Fold a piece of paper flat and make one straight cut. Now unfold the pieces and see what you get. It is known that, somewhat surprisingly, you can get any shape you like with this process. However, some shapes require folding patterns that are rather difficult to fold. Sometimes, only small changes in the desired shape can make a huge difference in the complexity of the folding pattern. The goal of this project is to formalize measures for the complexity of folding patterns, define algorithmic problems that aim to minimize the complexity, study their computational complexity, and provide a proof-of-concept implementation of the most promising algorithms. Examples for such problems could be: Given a polygon, what is the closest shape that results in a folding pattern with sufficiently low complexity? For each vertex of a given polygon, what are the alternative positions that yield a local minimum in complexity?
FLaMeCaST
- Datum: Di, 29 Okt 2024, 14:00
- Ort: SR 301
- Vortragende(r): Elly Schmidt, Henrik Csöre, PdF Abschlussvortrag
Flipping Non-Crossing Spanning Trees on Convex Point Sets
- Datum: Fr, 25 Okt 2024, 14:00
- Ort: SR 301
- Vortragende(r): Torsten Ueckerdt
- Inhalt: I will present our results on the diameter of the flip graph of non-crossing spanning trees on a set of n points in convex position. The corresponding paper has just been accepted at SODA 2025. The talk will be about 1h long.
Tree-Independence Number and Tree-Chromatic Number of Graphs
- Datum: Fr, 18 Okt 2024, 14:30
- Ort: SR 301
- Vortragende(r): Kilian Krause, Msc-Abschluss (Ueckerdt)
Generating Geometric Random Graphs with Boolean Distance Functions
- Datum: Fr, 18 Okt 2024, 14:00
- Ort: 101 (Sitzungszimmer)
- Vortragende(r): Maxime Rambaud, BA Vortrag
Frontiers of Randomised Data Structures
- Datum: Di, 15 Okt 2024, 13:00
- Ort: SR 301
- Vortragende(r): Stefan Walzer
- Inhalt: In this talk I give an overview over the research that I have carried out within the last 10 years and the research I plan to do in the future, mostly concerning hash tables and related data structures. Since a lot of my work involves random graphs, there is reason to believe that the Bläsius group has relevant expertise. In other words, I'm fishing for collaborators. The talk will be mostly identical to another talk of mine around the same time -- designed to convince the KiKIT board to fund a young investigator group led by me -- with a shift in focus.
Completeness Theorems for k-SUM and Geometric Friends
- Datum: Do, 10 Okt 2024, 14:00
- Ort: Virtual Talk
- Vortragende(r): Geri Gokaj
- Inhalt: Join Zoom Meeting https://kit-lecture.zoom-x.de/j/66867691192?pwd=0Im2eHf9vmaWGx9SVFjO2Xa5hOksh0.1 Meeting ID: 668 6769 1192 Passcode: 1VrfsZ@.
Recognizing and Coloring Directional and Bidirectional Interval Graphs
- Datum: Fr, 4 Okt 2024, 14:00
- Ort: SR 301
- Vortragende(r): Christoph Hoffmeyer, Msc-Thesis (Ueckerdt)
Sommersemester 2024
PdF Abschlussvortrag
- Datum: Fr, 27 Sep 2024, 15:00
- Ort: SR 301
- Vortragende(r): Deborah Haun
Bounding the Face Length of Girth-Planar Maximal Graphs
- Datum: Fr, 27 Sep 2024, 14:30
- Ort: SR 301
- Vortragende(r): Leon Kießle, Bsc-Thesis (Ueckerdt)
Freeze Tag Cop Number of Graphs
- Datum: Fr, 27 Sep 2024, 14:00
- Ort: SR 301
- Vortragende(r): Jonas Dalchow
Enumerating Alternative Paths
- Datum: Di, 24 Sep 2024, 13:45
- Ort: SR 301
- Vortragende(r): Tim Domnick, Bachelorarbeit
Hyperbolic Sphericity
- Datum: Fr, 20 Sep 2024, 14:00
- Ort: SR 301
- Vortragende(r): Lennart Großkrkeutz
Intersection Graphs with and without Product Structure
- Datum: Fr, 13 Sep 2024, 10:00
- Ort: SR 301
- Vortragende(r): Samuel Schneider, GD Probevortrag
- Inhalt: A graph class $mathcal{G}$ admits emph{product structure} if there exists a constant $k$ such that every $G in mathcal{G}$ is a subgraph of $H oxtimes P$ for a path $P$ and some graph $H$ of treewidth~$k$. Famously, the class of planar graphs, as well as many beyond-planar graph classes are known to admit product structure. However, we have only few tools to prove the absence of product structure, and hence know of only a few interesting examples of classes. Motivated by the transition between product structure and no product structure, we investigate subclasses of intersection graphs in the plane (e.g., disk intersection graphs) and present necessary and sufficient conditions for these to admit product structure. Specifically, for a set $S subset mathbb{R}^2$ (e.g., a disk) and a real number $alpha in [0,1]$, we consider emph{intersection graphs of $alpha$-free homothetic copies of $S$}. That is, each vertex $v$ is a homothetic copy of $S$ of which at least an $alpha$-portion is not covered by other vertices, and there is an edge between $u$ and $v$ if and only if $u cap v eq emptyset$. For $alpha = 1$ we have contact graphs, which are in most cases planar, and hence admit product structure. For $alpha = 0$ we have (among others) all complete graphs, and hence no product structure. In general, there is a threshold value $alpha^*(S) in [0,1]$ such that $alpha$-free homothetic copies of $S$ admit product structure for all $alpha > alpha^*(S)$ and do not admit product structure for all $alpha < alpha^*(S)$. We show for a large family of sets $S$, including all triangles and all trapezoids, that it holds $alpha^*(S) = 1$, i.e., we have no product structure, except for the contact graphs (when $alpha= 1$). For other sets $S$, including regular $n$-gons for infinitely many values of $n$, we show that $0 < alpha^*(S) < 1$ by proving upper and lower bounds.
Planar Graphs With Bounded Treewidth and Their Upward Stack Number
- Datum: Di, 3 Sep 2024, 13:00
- Ort: SR 301
- Vortragende(r): Samuel Schneider
TBA
- Datum: Di, 27 Aug 2024, 13:00
- Ort: SR 301
- Vortragende(r): Henry-Sinclair Banks, University of Warwick
Computing the Diameter of Toroidal Random Geometric Graphs
- Datum: Fr, 23 Aug 2024, 14:30
- Ort: SR 301
- Vortragende(r): Annemarie Schaub, Abschlusspräsentation Bachelorarbeit (Scale)
- Inhalt: TBD
Edge Densities and the Density Formula
- Datum: Fr, 23 Aug 2024, 14:00
- Ort: SR 301
- Vortragende(r): Benedikt Hahn, Msc-Arbeit Ueckerdt
Exploring the Approximability Landscape of 3SUM
- Datum: Fr, 16 Aug 2024, 14:00
- Ort: Virtual Talk
- Vortragende(r): Ahmed Ghazy, CISPA, Saarbrücken
- Inhalt: Join Zoom Meeting https://kit-lecture.zoom-x.de/j/66467670689?pwd=Z6GGJKRU8biamK5rNMXLieUA2BZ0Lp.1 Meeting ID: 664 6767 0689 Passcode: C3t!se7c
PdF short presentation(s)
- Datum: Di, 13 Aug 2024, 13:00
- Ort: SR 301
- Vortragende(r): PdF student(s)
Epistemic EFX Allocations Exist for Monotone Valuations
- Datum: Di, 6 Aug 2024, 13:30
- Ort: SR 301
- Vortragende(r): Hannaneh Akrami, MPI Informatics, Saarbrücken
- Inhalt: We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is considered to be one of the most fascinating fairness concepts in this line of work. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. introduced a promising relaxation of EFX, called epistemic EFX (EEFX). We say an allocation to be EEFX if, for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes "EFX-satisfied". Caragiannis et al. prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive? We address this important open question and answer it affirmatively by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations. To the best of our knowledge, EEFX is the only known relaxation of EFX (beside EF1) to have such strong existential guarantees. Furthermore, we complement our existential result by proving computational and information-theoretic lower bounds. We prove that even for an arbitrary number of (more than one) agents with identical submodular valuations, it is PLS-hard to compute EEFX allocations and it requires exponentially-many value queries to do so.
Computing Graph Hyperbolicity Using Dominating Sets
- Datum: Di, 6 Aug 2024, 13:00
- Ort: SR 301
- Vortragende(r): André Nusser, CNRS, Inria Center at Université Côte d’Azur
- Inhalt: Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning all quadruples of the graph or using fast matrix multiplication as building block, both are not practical for large graphs. In this paper, we propose and evaluate an approach that uses a hierarchy of distance-k dominating sets to reduce the search space. This technique, compared to the previous best practical algorithms, enables us to compute the hyperbolicity of graphs with unprecedented size (up to a million nodes).
Reduktionsregeln für k-Power Dominating Set
- Datum: Fr, 28 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Tobias Hoch, BA Kurzvortrag
On Wegner`s Conjecture for Rectangle Intersection Graphs
- Datum: Fr, 21 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Anouk Sommer, Bsc-Defense Ueckerdt
Edge Densities and the Density Formula
- Datum: Fr, 14 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Benedikt Hahn, Msc-Ueckerdt Kurzvortrag
Einsichten zur Lösbarkeit von Solarparkverkabelungs-Problemen
- Datum: Di, 11 Jun 2024, 13:00
- Ort: SR 301
- Vortragende(r): Thomas Oltmann, MA Abschlussvortrag
PdF Vorträge
- Datum: Fr, 7 Jun 2024, 14:15
- Ort: SR 301
- Vortragende(r): Sven, Elly und Henrik, Deborah
Freeze Tag Cop Number of Graphs
- Datum: Fr, 7 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Jonas Dalchow
Solo Chess
- Datum: Fr, 24 Mai 2024, 14:30
- Ort: SR 301
- Vortragende(r): Kolja Kühn, Kurzvortrag
Kurzvortrag: Stack Number of Upwards Planar k-Trees
- Datum: Fr, 24 Mai 2024, 14:15
- Ort: SR 301
- Vortragende(r): Samuel Schneider
- Inhalt: The stack number of a directed acyclic graph G is the minimum k for which there exists a topological ordering v_1, … , v_n of G and a k-coloring of the edges such that each edge v_iv_j with i < j has a different color than all edges v_i’vj’ with i < i’
Enumerating Alternative Paths
- Datum: Fr, 24 Mai 2024, 14:00
- Ort: SR 301
- Vortragende(r): Tim Domnick, Kurzvortrag
Hyperbolic Sphericity
- Datum: Fr, 17 Mai 2024, 14:00
- Ort: SR 301
- Vortragende(r): Lennart Großkrkeutz, BA Kurzvortrag
How to Reduce Temporal Cliques to Find Sparse Spanners
- Datum: Fr, 10 Mai 2024, 14:15
- Ort: SR 301
- Vortragende(r): Sebastian Angrick, M.Sc. student at HPI Potsdam
- Inhalt: Many real-world networks, like transportation networks and social networks, are dynamic in the sense that the edge-set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with O(n log n) many edges. We present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques.
Computing the Diameter of Toroidal Random Geometric Graphs
- Datum: Fr, 10 Mai 2024, 14:00
- Ort: SR 301
- Vortragende(r): Annemarie Schaub, Kurzvortrag Bachelorarbeit (scale)
Multi Via-Node Alternatives for Customized Contraction Hierarchies
- Datum: Fr, 3 Mai 2024, 14:00
- Ort: SR 301
- Vortragende(r): Scott Bacherle, Bachelor Student
- Inhalt: Sometimes in a road network, the shortest path between two points is not the only desirable path for road users. The problem of finding alternative paths is well studied and there are many existing algorithms. Alternatives can be found quickly with customizable contraction hierarchies, however these algorithms are outperformed by others. We propose a novel method to find alternative paths by splitting a shortest path into smaller subpaths and searching for alternatives for each one. The alternatives for the subpaths are then linked to form alternatives for the complete path. We study its performance and success rate compared to existing CCH-based algorithms, determining that a combined approach finds more paths with only marginally higher average runtime.
On the Computational Complexity of Doors
- Datum: Fr, 19 Apr 2024, 14:30
- Ort: SR 301
- Vortragende(r): Oguz Mutlu
Theoretical Study of Data Reduction in Real-World Hitting Set Instances
- Datum: Fr, 19 Apr 2024, 14:00
- Ort: SR 301
- Vortragende(r): Marcus Wunderlich, master defense (scale)
- Inhalt: Finding a minimum HittingSet is a fundamental optimization problems on hypergraphs. Despite being N P-complete and even W[2]-complete (if parametrized by solution size), many real-world instances can be solved quickly due to two simple reduction rules by Weihe [Wei98]. Experiments show that heterogeneity and locality are both common properties of real-world instances as well as crucial factors for the effectiveness of these reduction rules. In this thesis, we analyze a random model similar to 1D-GIRGs that generates hypergraphs with adjustable degrees of heterogeneity and locality from a theoretical perspective. For the model’s threshold variant, where the locality is set to its maximum, we show that the reduction rules reduce the generated hypergraphs to a trivial kernel under weak conditions that depend on the degree of heterogeneity. We, additionally, provide a fix to solve these instances that do not satisfy this condition. For a general level of locality, we find that at least a significant constant percentage of vertices is expected to be eliminated by the reduction rules, depending on the degree of both heterogeneity and locality..
Engineering Algorithms for CP-Treewidth
- Datum: Fr, 12 Apr 2024, 14:00
- Ort: SR 301
- Vortragende(r): Tobias Gröger, Abschlusspräsentation Bachelorarbeit (Scale)
- Inhalt: Dynamic programming is a powerful and much used technique in the design of fixed-parameter tractable (FPT) algorithms for NP-hard problems. However, there is a distinct lack of high performance implementations of these algorithms. Thus, we develop such an implementation on a clique-partitioned tree decompositions to solve the Maximum Independent Set problem with a focus on its optimization and evaluation. First, we improve a well known version of this dynamic program and consider relevant aspects for a practical implementation. We show that, while the cp-treewidth is a better parameter to estimate the runtime of this dynamic program than the treewidth, the clique-partitioning structure is not required, thus our algorithm operates on a regular tree decomposition. In addition, we consider the application of reduction rules and lower and upper bound pruning. Even though pruning seems to be effective in theory, it leads to a higher variation in runtime depending on the choice of root and we were unable to achieve any benefits in practice. However, the reductions rules are highly effective for most instances. We find that only with reduction rules our algorithm outperforms other solvers on instances with a low cp-treewidth.
Wintersemester 2023
PdF Abschlussvortrag
- Datum: Fr, 22 Mär 2024, 15:00
- Ort: SR 301
- Vortragende(r): Lena Scherzer
Induced Turan problems on bipartite host graphs
- Datum: Fr, 22 Mär 2024, 14:30
- Ort: SR 301
- Vortragende(r): Jakob Zimmermann, Bsc Abschlussvortrag Ueckerdt
Complexity of the Sum of Square Roots Problem
- Datum: Fr, 22 Mär 2024, 14:00
- Ort: SR 301
- Vortragende(r): Jonathan Hunz, ITI Wagner, Bachelorarbeit
- Inhalt: The task of comparing sums of square roots is inevitable in many geometric problems in Euclidean space, e.g. the Euclidean traveling salesman or Euclidean Steiner tree problem. The Sum of Square Roots Problem is a notorious open problem since the 1970s and placing it in the vast landscape of complexity classes has been an ongoing challenge. Allender, Bürgisser, Kjeldgaard-Pedersen and Miltersen showed in 2009 that the Sum of Square Roots Problem lies within the Counting Hierarchy CH in their paper "On the Complexity of Numerical Analysis". To date, no stronger upper bound for the complexity of this problem, let alone a placement in a well studied complexity class like P, NP or the Polynomial Hierarchy PH is known. In this work, we present the proof of Allender et al. and unpack its complicated intermediate steps.
A Practical Evaluation of Modular Decomposition Algorithms
- Datum: Mi, 20 Mär 2024, 13:30
- Ort: SR 301
- Vortragende(r): Jonas Spinner
Defining the Discrete Real Polynomial Hierarchy with Oracle Machines
- Datum: Fr, 1 Mär 2024, 14:00
- Ort: SR 301
- Vortragende(r): Illia Minkin, ITI Wagner, Bachelorarbeit
- Inhalt: Die kürzlich eingeführte Komplexitätsklasse ER spielt eine wichtige Rolle in der algorithmischen Geometrie. Diese Klasse kann ähnlich zur polynomiellen Hierarchie verallgemeinert werden - dadurch erhält man die sogenannte diskrete reelle polynomielle Hierarchie DRPH. Im Gegensatz zur klassischen Polynomialzeithierarchie, die üblicherweise mithilfe von Orakel-Turingmaschinen definiert wird, wird DRPH klassischerweise über vollständige Probleme eingeführt.
Die „Orakel-Notation“ ist nicht nur intuitiv, sondern spiegelt die Struktur von Problemen in den entsprechenden Komplexitätsklassen wider. Es ist erstrebenswert, diese Notation auch für DRPH zu verwenden, allerdings ist solch eine Notation ohne ein passendes Berechnungsmodell nicht wohldefiniert. Das Ziel dieser Arbeit ist es, ein passendes Orakel-Berechnungsmodell zu finden und DRPH damit zu definieren. Wir fassen relevante Ergebnisse aus der klassischen Komplexitätstheorie zusammen und führen die BSS sowie die reellen RA (random access) Maschinen ein. Danach stellen wir die existentielle Theorie der reellen Zahlen sowie die entsprechende Komplexitätsklasse ER vor. Schlussendlich führen wir die diskrete reelle polynomielle Hierarchie ein und definieren diese mithilfe von Orakel BSS und reellen RA Maschinen. Dies ist ein zentrales Ergebnis der Thesis. Überdies diskutieren wir, wie die nullte Stufe von DRPH definiert werden kann.
Kurzvortrag: Euclidean Solar Farm Cable Layout Problem
- Datum: Fr, 23 Feb 2024, 14:15
- Ort: SR 301
- Vortragende(r): Elly Schmidt, Henrik Csöre
Kurzvortrag: Grids in Hyperbolic Unit Disk Graphs
- Datum: Fr, 23 Feb 2024, 14:00
- Ort: SR 301
- Vortragende(r): Deborah Haun
On Wegner's Conjecture for Rectangle Intersection Graphs
- Datum: Fr, 2 Feb 2024, 14:00
- Ort: SR 301
- Vortragende(r): Anouk Sommer, Kurzvortrag - Bsc-thesis
Complexity of the Solar Farm Cable Layout Problem
- Datum: Fr, 12 Jan 2024, 14:15
- Ort: SR 301
- Vortragende(r): Thomas Oltmann
Defining the Discrete Real Polynomial Hierarchy with Oracle Machines
- Datum: Fr, 12 Jan 2024, 14:00
- Ort: SR 301
- Vortragende(r): Illia Minkin
- Inhalt: Kurzvortrag, ITI Wagner
Multi Via Node Alternatives for CCH
- Datum: Fr, 15 Dez 2023, 14:30
- Ort: SR 301
- Vortragende(r): Scott Bacherle, BA
Complexity of the Sum of Square Roots Problem
- Datum: Fr, 15 Dez 2023, 14:00
- Ort: SR 301
- Vortragende(r): Jonathan Hunz
- Inhalt: Kurzvortrag BA ITI Wagner
On the Computational Complexity of Doors
- Datum: Fr, 1 Dez 2023, 15:00
- Ort: SR 301
- Vortragende(r): Oguz Mutlu
Engineering Algorithms for CP-Treewidth
- Datum: Fr, 1 Dez 2023, 14:30
- Ort: SR 301
- Vortragende(r): Tobias Gröger, Kurzvortrag Bachelorarbeit
Heuristics for System Optimal Traffic Assignment
- Datum: Fr, 1 Dez 2023, 14:00
- Ort: SR 301
- Vortragende(r): Jan Erik Voigt, Bachelorarbeit
On the Effectiveness of Reduction Rules for Hitting Set
- Datum: Fr, 17 Nov 2023, 14:00
- Ort: SR 301
- Vortragende(r): Marcus Wunderlich, MA Kurzvortrag
Inverse Traffic Assignment
- Datum: Mi, 8 Nov 2023, 15:00
- Ort: SR 236
- Vortragende(r): Markus Jung, Bachelor Student
- Inhalt: Traffic Assignment beschäftigt sich mit der Vorhersage des Verhaltens von Verkehrsteilnehmern, um die Auslastung eines Straßennetzwerks zu ermitteln. Inverse Traffic Assignment strebt eine neue Art der Zuordnung von Verkehrsteilnehmern zu gemeinsam befahrenen Routen in einem urbanen Straßennetzwerk an, welche die wirksame Bekämpfung der durch steigende Verkehrsnachfrage ausgelösten Probleme ermöglichen soll. Im urbanen Raumentstehen beim Transport von Verkehrsteilnehmern in Einzelfahrzeugen hohe Schadstoffemissionen und hoher Energieverbrauch. Für Inverse Traffic Assignment wird die Routenwahl der Verkehrsteilnehmer unter der Annahme vorhergesagt, dass ein hohes Verkehrsaufkommen zusätzliche Anreize schafft, die entsprechende Route zu befahren. In dieser Arbeit wird ein iteratives Verfahren vorgestellt, dass gemäß dieser Anreize die aus der Routenwahl der Verkehrsteilnehmer resultierende Netzwerkauslastung bestimmt. Dabei soll sich der Verkehr auf wenige stark befahrene Straßen im Netzwerk konzentrieren. Motiviert wird das Vorgehen durch die Annahme, dass auf Routen mit hohem resultierenden Verkehrsaufkommen ein Ausbau der Möglichkeiten für die Reise in öffentlichen und geteilten Verkehrsmitteln besonders wirksam Emissionen und Energieverbrauch pro Verkehrsteilnehmer reduzieren kann, während weite Teile des Straßennetzwerks entlastet werden. Bei Tests des iterativen Verfahrens auf einem urbanen Straßennetzwerk für verschiedene Eingaben stellt sich ein stabiler Zustand des Verkehrsaufkommens nach wenigen Iterationen ein und es kann das gewünschte Resultat eines auf eine kleine Anzahl an Routen konzentrierten Verkehrsaufkommens beobachtet werden.
The Ramsey Turnaround Number
- Datum: Fr, 3 Nov 2023, 14:00
- Ort: SR 301
- Vortragende(r): Nora Almasi, Masterarbeit Wagner/Ueckerdt
Exploring Clique-Partitioned Treewidth
- Datum: Fr, 6 Okt 2023, 14:00
- Ort: SR 236
- Vortragende(r): Sven Geißler, Abschlusspräsentation Bachelorarbeit
- Inhalt: Clique-partitioned treewidth is a parameter for graphs that is similar to treewidth but additionally considers the structure of each bag. This is achieved by partitioning the vertices of each bag into cliques and assigning each bag a weight based on the logarithmic sizes of its cliques. In this thesis, we use this parameter to design parametrized algorithms for many $mathcal{NP}$-complete problems and give a general framework for such algorithms. For designing those algorithms, we adapt already known normalizations of tree decompositions to clique-partitioned tree decompositions and introduce a new type of normalization called smooth clique-partitioned tree decomposition. Furthermore, we prove that FPT-algorithms for problems parametrized by clique-partitioned treewidth can be found if and only if such algorithms can be found for treewidth. Building on this, we prove for a large number of problems that giving algorithms with clique-partitioned treewidth that are substantially faster than their direct treewidth-counterparts is impossible under the Exponential-Time Hypothesis. Here, we prove that those problems admit single exponential algorithms when parametrizing by treewidth but only double exponential algorithms for clique-partitioned treewidth. We also show that introducing an additional parameter, like the newly defined clique-degree, can allow us to describe parametrized algorithms for those problems. To better understand the parameter, we compare it to related parameters and study its behaviour on some graph families.
Sommersemester 2023
Product Structure of alpha-free Intersection Graphs
- Datum: Fr, 29 Sep 2023, 14:30
- Ort: SR 301
- Vortragende(r): Samuel Schneider, Praxis der Forschung
- Inhalt: A graph class $\mathcal{G}$ has product structure if there exists an integer c such that for all graphs G in $\mathcal{G}$ there exist a graph H with treewidth at most c and a path P such that $G \subseteq H \boxtimes P$. Product structure has recently been shown for various beyond-planar graph classes and was used to improve bounds on several graph parameters. We examine a new class of geometric intersection graphs with shapes as vertices in regards of the existence of product structure, that we call alpha-free intersection graphs for 0 <= alpha <= 1. An intersection graph is $alpha$-free if each shape has at least $alpha$ of its area disjoint from any other shape. We show that for $alpha$-free intersection graphs of homothetic triangles or trapezoids product structure exists if and only if alpha = 1, i.e. when the shapes are internally disjoint.
Towards Product Structure of Hyperbolic Disk Graphs
- Datum: Fr, 29 Sep 2023, 14:00
- Ort: SR 301
- Vortragende(r): Dominik Sucker, Bachelorarbeit
Efficient Embedding of Scale-Free Graphs in a Weighted Geometric Space
- Datum: Fr, 15 Sep 2023, 14:30
- Ort: SR 301
- Vortragende(r): Markus Wünstel
Robustness of the Discrete Real Polynomial Hierarchy
- Datum: Fr, 15 Sep 2023, 08:30
- Ort: SR 301
- Vortragende(r): Tim Junginger, ITI Wagner, Bachelorarbeit
- Inhalt: Wir betrachten die diskrete reelle polynomielle Hierarchie; ein Analogon zur polynomiellen Hierarchie, aber über den reellen Zahlen. Diese erweitern wir um drei exotische Quantoren: E* (exists^*), A* (forall^*) und H. Wir motivieren die Nützlichkeit dieser Quantoren und stellen eine "Robustheitsvermutung" auf. Die Ergebnisse aus der dazugehörigen Bachelorarbeit zeigen Robustheit bis zur zweiten Stufe und lassen sich zu Teilen auf alle höheren Stufen übertragen.
An Efficient Algorithm for Power Dominating Set
- Datum: Fr, 1 Sep 2023, 14:30
- Ort: SR 301
- Vortragende(r): Max Göttlicher, Probevortrag ESA
MA intro: Modular Decomposition In Practice
- Datum: Fr, 1 Sep 2023, 14:00
- Ort: SR 301
- Vortragende(r): Jonas Spinner
Crossing-Minimal Point-Set Embedding
- Datum: Fr, 28 Jul 2023, 14:00
- Ort: SR 301
- Vortragende(r): Graph Drawing Praktikum, Abschlussvorträge
- Inhalt: Abschlussvorträge aus dem Graph Drawing Praktikum. Drei Vorträge von jeweils 20 Minuten. Aufgabe: https://mozart.diei.unipg.it/gdcontest/2023/live/
Kurzvortrag
- Datum: Fr, 14 Jul 2023, 14:30
- Ort: SR 301
- Vortragende(r): Jan-Erik Voigt, Bachelor Student
Induced Subgraphs With Unbounded Treewidth
- Datum: Fr, 14 Jul 2023, 14:00
- Ort: SR 301
- Vortragende(r): Samuel Schneider, Praxis der Forschung
Partitioning the Bags of a Tree Decomposition Into Cliques (SEA preview talk)
- Datum: Fr, 7 Jul 2023, 14:30
- Ort: SR 301
- Vortragende(r): Marcus Wilhelm, ITI Scale
- Inhalt: We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algorithms based on similar parameters for various problems. With this paper, we take a first step towards computing clique-partitioned tree decompositions. Our focus lies on the subproblem of computing clique partitions, i.e., for each bag of a given tree decomposition, we compute an optimal partition of the induced subgraph into cliques. The goal here is to minimize the product of the clique sizes (plus 1). We show that this problem is NP-hard. We also describe four heuristic approaches as well as an exact branch-and-bound algorithm. Our evaluation shows that the branch-and-bound solver is sufficiently efficient to serve as a good baseline. Moreover, our heuristics yield solutions close to the optimum. As a bonus, our algorithms allow us to compute first upper bounds for the clique-partitioned treewidth of real-world networks. A comparison to traditional treewidth indicates that clique-partitioned treewidth is a promising parameter for graphs with high clustering.
Kurzvortrag (Inverse Traffic Assignment)
- Datum: Fr, 7 Jul 2023, 14:00
- Ort: SR 301
- Vortragende(r): Markus Jung, Bachelor Student
Kurzvortrag: Towards Product Structure of Hyperbolic Disc Graphs
- Datum: Fr, 30 Jun 2023, 14:30
- Ort: SR 301
- Vortragende(r): Dominik Sucker, Bachelorarbeit
- Inhalt: Dvorak et al. [Matrix Annals 2021] have shown that Euclidian unit disc graphs have product structure. This has, however, not yet been shown for hyperbolic disc graphs. We consider this question by generalising the approach of Dvorak et al. and trying to apply it to hyperbolic disc graphs.
Arc-Flags Meet Trip-Based Public Transit Routing
- Datum: Fr, 30 Jun 2023, 14:00
- Ort: SR 301
- Vortragende(r): Patrick Steil, Probevortrag SEA
- Inhalt: We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over b, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks.
Solving Power Dominating Set with Branch and Bound
- Datum: Di, 27 Jun 2023, 13:00
- Ort: SR 301
- Vortragende(r): Julia Lutzweiler, Abschlussvortrag MA
- Inhalt: Power dominating set is a graph problem that asks for the smallest subset of vertices that can observe all vertices. Observation is defined by two rules. The first one states that all neighbors of the power dominating set are observed. This is identical to dominating set, of which power dominating set is an extension. The second rule allows for propagation of the observation status to vertices that are the only unobserved neighbor of an observed vertex. Like dominating set, power dominating set is NP-complete. Multiple approaches for solving power dominating set have been presented across literature, including a formulation as an integer linear program. In this thesis, we present an algorithm based on branch and bound. We derive a variety of lower and upper bounds to the optimal solution and relate power dominating set to a graph covering problem. Moreover, we discuss different strategies for branching. The implementation of our algorithm outperforms the reference solution based on an integer linear program for small graphs but is slower on larger instances.
The Real Polynomial Hierarchy
- Datum: Fr, 23 Jun 2023, 14:00
- Ort: SR 301
- Vortragende(r): Tim Junginger, ITI Wagner, Bachelorarbeit, Kurzvortrag
Towards the Evaluation of Graph Embeddings with Deep Decoders
- Datum: Fr, 16 Jun 2023, 14:30
- Ort: SR 301
- Vortragende(r): Paul Wagner
- Inhalt: Bachelor thesis presentation
Graph Representations using Tetrahedra Contact Representations
- Datum: Fr, 16 Jun 2023, 14:00
- Ort: SR 301
- Vortragende(r): Tobias Knorr, Abschlussvortrag Msc -- ITI Wagner
Dynamic Flows with Time-Dependent Capacities
- Datum: Fr, 26 Mai 2023, 14:30
- Ort: SR 301
- Vortragende(r): Adrian Feilhauer
- Inhalt: Dynamic network flows, sometimes called flows over time, extend the notion of network flows to include a transit time for each edge. While Ford and Fulkerson showed that certain dynamic flow problems can be solved via a reduction to static flows, many advanced models considering congestion and time-dependent networks result in NP-hard problems. To increase understanding of these advanced dynamic flow settings we study the structural and computational complexity of the canonical extensions that have time-dependent capacities or time-dependent transit times. If the considered time interval is finite, we show that already a single edge changing capacity or transit time once makes the dynamic flow problem weakly NP-hard. In case of infinite considered time, one change in transit time or two changes in capacity make the problem weakly NP-hard. For just one capacity change, we conjecture that the problem can be solved in polynomial time. Additionally, we show the structural property that dynamic cuts and flows can become exponentially complex in the above settings where the problem is NP-hard. We further show that, despite the duality between cuts and flows, their complexities can be exponentially far apart.
Towards a Theoretical Analysis of the Routing Architecture KIRA
- Datum: Fr, 26 Mai 2023, 14:00
- Ort: SR 301
- Vortragende(r): Wendy Yi
- Inhalt: With the increasing sizes of networks, the demand for more scalable and dynamic routing algorithms on networks grows. KIRA is a newly developed routing architecture for networks which consists of the ID-based routing protocol R^2/Kad. Experiments suggest that R^2/Kad is able to provide control plane connectivity, and to find short paths in most cases, while being highly scalable and robust. We initiate a theoretical analysis on properties of KIRA such as connectivity and the quality of the found routes.
Exploring Clique-Partitioned Treewidth
- Datum: Fr, 12 Mai 2023, 14:00
- Ort: SR 301
- Vortragende(r): Sven Geißler, BA Kurzvortrag (Scale)
- Inhalt: In a clique-partitioned tree-decomposition of a graph G, we annotate each bag X with a partition of G[X] into cliques C_i, such that the sum of log(|C_i|+1) is low. In this thesis we explore the tractability of different problems under this parameter.
Minimal Asymmetric Hypergraphs
- Datum: Fr, 28 Apr 2023, 14:00
- Ort: SR 301
- Vortragende(r): Dominik Bohnert, Abschlussvortrag Bsc - ITI Wagner
- Inhalt: An k-graph is a hypergraph where every edge has size k. If every automorphism on a k-graph G is the identity we say that G is asymmetric. Furthermore we call G minimal asymmetric, if G is asymmetric and every non trivial induced subgraph on at least two vertices of G is not asymmetric. In 2016 Schweitzer and Schweitzer confirmed a conjecture by Nesetril that there are only finitely many minimal asymmetric graphs. In this thesis we study minimal asymmetry of k-graphs. We extend a result by Jiang and Nesetril to show, that in contrast to the case k = 2, for every k at least 3 there are infinitely many asymmetric k-graphs that are linear and have maximum degree 2. We generalize the concept of the degree of asymmetry introduced to graphs by Erdoes and Renyi to the setting of k-graphs. Then we consider regular asymmetric k-graphs which have some interior symmetry as every vertex has the same degree. To conclude we survey an algorithm due to Luks that decides in simply exponential running time whether a given hypergraph is minimal asymmetric.
Efficient Embedding of Scale-Free Graphs in a Weighted Geometric Space
- Datum: Di, 25 Apr 2023, 13:00
- Ort: SR 236
- Vortragende(r): Markus Wünstel
Komplexitätsanalyse des Lawn Mowing Problems und verwandter Probleme
- Datum: Fr, 21 Apr 2023, 14:00
- Ort: SR 301
- Vortragende(r): Mirco Volk, Bachelorarbeit
Cable Layout Optimization Problems in the Context of Renewable Energy Sources
- Datum: Mo, 17 Apr 2023, 14:00
- Ort: SR 301
- Vortragende(r): Sascha Gritzbach, Probevortrag Verteidigung
Geometric Inhomogeneous Random Graphs for Algorithm Engineering
- Datum: Do, 6 Apr 2023, 14:00
- Ort: SR 301
- Vortragende(r): Chris, Probevortrag Verteidigung
- Inhalt: The design and analysis of graph algorithms is heavily based on the worst case. In practice, however, many algorithms perform much better than the worst case would suggest. Furthermore, various problems can be tackled more efficiently if one assumes the input to be, in a sense, realistic. The field of network science, which studies the structure and emergence of real-world networks, identifies locality and heterogeneity as two frequently occurring properties. A popular model that captures these properties are geometric inhomogeneous random graphs (GIRGs), which is a generalization of hyperbolic random graphs (HRGs). Aside from their importance to network science, GIRGs can be an immensely valuable tool in algorithm engineering. Since they convincingly mimic real-world networks, guarantees about quality and performance of an algorithm on instances of the model can be transferred to real-world applications. They have model parameters to control the amount of heterogeneity and locality, which allows to evaluate those properties in isolation while keeping the rest fixed. Moreover, they can be efficiently generated which allows for experimental analysis. While realistic instances are often rare, generated instances are readily available. Furthermore, the underlying geometry of GIRGs helps to visualize the network, e.g.,~for debugging or to improve understanding of its structure. The aim of this work is to demonstrate the capabilities of geometric inhomogeneous random graphs in algorithm engineering and establish them as routine tools to replace previous models like the ErdH{o}s-R{'e}nyi model, where each edge exists with equal probability. We utilize geometric inhomogeneous random graphs to design, evaluate, and optimize efficient algorithms for realistic inputs. In detail, we provide the currently fastest sequential generator for GIRGs and HRGs and describe algorithms for maximum flow, directed spanning arborescence, cluster editing, and hitting set. For all four problems, our implementations beat the state-of-the-art on realistic inputs. On top of providing crucial benchmark instances, GIRGs allow us to obtain valuable insights. Most notably, our efficient generator allows us to experimentally show sublinear running time of our flow algorithm, investigate the solution structure of cluster editing, complement our benchmark set of arborescence instances with a density for which there are no real-world networks available, and generate networks with adjustable locality and heterogeneity to reveal the effects of these properties on our algorithms.