Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2010
Forschungsseminar

Forschungsseminar

Wintersemester 2024

Weighted Embeddings for Low-Dimensional Graph Representation

  • Datum: Mi, 22 Jan 2025, 14:00
  • Ort: SR 301
  • Vortragende(r): Jean-Pierre von der Heydt

tba

  • Datum: Mi, 15 Jan 2025, 14:00
  • Ort: SR 301
  • Vortragende(r): Torsten Ueckerdt

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&#39;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&#39;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.

Wintersemester 2022

Projektantrag: Necessary and Sufficient Conditions for the Existence of a Product Structure

  • Datum: Fr, 31 Mär 2023, 15:00
  • Ort: SR 301
  • Vortragende(r): Lena Scherzer, Samuel Schneider, Praxis der Forschung

The Complexity of the Oriented Cycle Game

  • Datum: Fr, 31 Mär 2023, 14:30
  • Ort: SR 301
  • Vortragende(r): Shabi Shabani, Bsc-Abschluss ITI-Wagner
  • Inhalt: The oriented cycle game, which was introduced by Bollobás and Szabó, is a strategy game played on undirected graphs in which both players, A(voider) and C(reator), assign orientations to undirected edges alternately until there are no more undirected edges. Unlike the original game, where player C tries to create a directed cycle and player A tries to prevent him, we introduce two new variations. First, we introduce the avoid oriented cycle game, where both players try to prevent a directed cycle. The first player to create a directed cycle loses. Next, we introduce the seek oriented cycle game, where both players try to create a directed cycle. The first player to create a directed cycle wins. Following, we introduce the oriented edge groups, which is a relation between oriented edges. Here, a player, when orienting an undirected edge, must orient the other edges that are in relation to the undirected edge accordingly.

Mixed Page Number of Planar Directed Acyclic Graphs

  • Datum: Fr, 31 Mär 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Deborah Haun, Bachelorarbeit
  • Inhalt: A q-queue s-stack layout consists of a topological ordering of the vertices of a graph and a partition of its edges into q sets of edges, called queues, and s sets of edges, called stacks, such that any two edges in the same queue do not nest and any two edges in the same stack do not cross. Here, two edges nest if the endpoints of one edge are located between the endpoints of the other edge. Two edges cross if their endpoints alternate in the topological ordering. The minimum number q + s of queues and stacks required for a q-queue s-stack layout is called the mixed page number. We investigate the mixed page number of upward planar graphs and directed acyclic 2-trees. We find a subclass of upward planar bipartite graphs whose mixed page number is bounded by a constant. In addition, we give a lower bound of 3 on the mixed page number of upward planar bipartite graphs and find an upward planar bipartite graph, whose mixed page number is strictly smaller than its stack and queue number. For directed acyclic 2-trees, we show that the mixed page number is unbounded. In contrast, we present a family of directed acyclic 2-trees with bounded mixed page number but unbounded stack and queue number.

LARA: Werkzeug zur Literaturrecherche

  • Datum: Fr, 31 Mär 2023, 13:30
  • Ort: SR 301
  • Vortragende(r): Gregor Czubayko, Paul David Gauer, Johannes Breitling, Linus Buck, Thomas Roth, Abschlusspräsentation PSE

On the Connection Between Exactly Solving and Approximating Vertex Cover

  • Datum: Mi, 29 Mär 2023, 14:00
  • Ort: SR 236
  • Vortragende(r): Carina Weber, Masterarbeit ITI Bläsius
  • Inhalt: This thesis investigates the greedy algorithm for the vertex cover problem, which selects a vertex with the highest degree at each step. Despite having an upper bound of O(log n) for the cover size, this bound is much higher than most ratios on real- world graphs. The problem has been studied previously, for example on hyperbolic random graphs, but we examine the impact of tie-breaking between vertices and the probability-distribution of all greedy vertex covers, instead of individual covers, which has not been adequately investigated. To this end we introduce an enumeration algorithm for all greedy vertex covers of a graph, which can be time-consuming, and thus we propose several optimizations to improve efficiency. Our experiments reveal that the optimizations are effective in reducing the running time and can handle larger graphs than before. Additionally, we demonstrate that the upper bound of O(log n) for the cover size of the greedy algorithm is not closely approached by any graph in our set concerning the ratio between the minimum and greedy cover size. According to the data we obtained from executing the enumeration algorithm on a set of graphs, we found that the cover size for these graphs increases with a ratio between 1.0 and 1.1 with high probability.

Kurzvortrag: Necessary and Sufficient Conditions for the Existence of a Product Structure

  • Datum: Fr, 10 Mär 2023, 14:30
  • Ort: SR 301
  • Vortragende(r): Lena Scherzer, Samuel Schneider, Praxis der Forschung
  • Inhalt: The row treewidth of a graph $G$ is the minimum integer $k$ such that a path $P$ and a graph $H$ exist with $ w(H) leq k$ and $G subseteq H oxtimes P$. A family of graphs $mathcal{G}$ has product structure if and only if the row treewidth of $mathcal{G}$ is bounded. A known necessary condition for the row treewidth to be bounded is emph{linear local treewidth}. However, it is unclear whether this condition is also sufficient. We want to examine intersection graphs of homothetic $alpha$-free triangles in the plane, meaning triangles with a certain amount $alpha$ of their area disjoint from any other triangle. While it is clear that for some $alpha$ the local treewidth is not linear, we want to examine whether there exists an $alpha$ such that the local treewidth is linear, but for which product structure does not exist. This would prove, that linear local treewidth is not sufficient for the existence of product structure.

Combining Geometric Inhomogeneous Random Graphs with the Stochastic Block Model

  • Datum: Fr, 10 Mär 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Florian Küfner, BA Abschlussvortrag

Towards Homogenizing Heterogeneous Graphs with Underlying Geometry

  • Datum: Fr, 3 Feb 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Nils Schewe, Bachelor Presentation

Efficiently Computing Directed Minimum Spanning Trees (ALENEX rehearsal)

  • Datum: Fr, 20 Jan 2023, 14:15
  • Ort: SR 301
  • Vortragende(r): Chris, Master (rating: 2124)
  • Inhalt: Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discussed an elegant solution. It was refined to run in $O(min(n^2, mlog n))$ by Tarjan which is optimal for very dense and very sparse graphs. Gabow et al.~gave a version of Edmonds' algorithm that runs in $O(nlog n + m)$, thus asymptotically beating the Tarjan variant in the regime between sparse and dense. Despite the attention the problem received theoretically, there exists, to the best of our knowledge, no empirical evaluation of either of these algorithms. In fact, the version by Gabow et al.~has never been implemented and, aside from coding competitions, all readily available Tarjan implementations run in $O(n^2)$. In this paper, we provide the first implementation of the version by Gabow et al.~as well as five variants of Tarjan's version with different underlying data structures. We evaluate these algorithms and existing solvers on a large set of real-world and random graphs.

queue and stack numbers and Boolean and DM-dimension of posets

  • Datum: Fr, 20 Jan 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Miriam Goetze, ITI Wagner -- Msc Kurzvortrag (15min)

Towards the Evaluation of Graph Embeddings with Deep Decoders

  • Datum: Mi, 18 Jan 2023, 13:00
  • Ort: SR 236
  • Vortragende(r): Paul Wagner

Komplexität des Lawn Mowing Problem

  • Datum: Fr, 13 Jan 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Mirco Volk, ITI Wagner, Bachelorarbeit, Kurzvortrag
  • Inhalt: Gegeben seien ein Polygon P und ein Rasenmäher in Form eines Einheitskreises. Wie schwierig ist es, eine kürzeste Route zu finden, die jeden Punkt des Polygons mäht.

Branching Algorithm for Power Domination Set

  • Datum: Fr, 16 Dez 2022, 14:45
  • Ort: SR 301
  • Vortragende(r): Julia Lutzweiler, MA Kurzvortrag

Theoretic Analysis of KIRA

  • Datum: Fr, 16 Dez 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Wendy Yi, MA Kurzvortrag

Classification of Gas Networks: A Graph-Theoretic Approach

  • Datum: Fr, 16 Dez 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Marc Jenne, ITI Wagner, Masterarbeit
  • Inhalt: Gas networks account for a large share of energy supply both in households and industry. They are present in all region types, such as large cities, rural areas and industrial areas. It is of interest to see whether gas networks can be classified based on the region type which they originate from. This is possible if gas networks from similar regions share important common characteristics and if gas networks from different regions differ significantly from each other. We present a graph-theoretic approach to characterise and classify gas networks originating from different region types. For this purpose, we model gas networks as graphs and examine several parameters that describe graphs from various perspectives. Using a data set of gas network instances with known origins, we analyse the common features and differences both between networks from the same region type and between networks from different types. Based on these analyses we find distinguishable gas network classes as well as meaningful parameters that characterise these classes.

Tetraeder-Kontaktdarstellungen

  • Datum: Mi, 14 Dez 2022, 13:00
  • Ort: SR 236
  • Vortragende(r): Tobias Knorr, Msc-Arbeit, Kurzvortrag (15min)

Random Minimum Spanning Trees in the Hyperbolic Plane

  • Datum: Mi, 7 Dez 2022, 13:00
  • Ort: SR 236
  • Vortragende(r): Yavor Lakov

Kurzvortrag: Mixed Page Number of Upward Planar Graphs

  • Datum: Fr, 2 Dez 2022, 14:15
  • Ort: SR 301
  • Vortragende(r): Deborah Haun
  • Inhalt: A directed graph is upward planar if it admits a planar drawing, where all edges are going upwards. A q-queue s-stack layout consists of a topological ordering of the vertices of a graph and a partition of its edges into q sets of edges, called queues, and s sets of edges, called stacks, such that any two edges in the same queue do not nest and any two edges in the same stack do not cross. Here, two edges nest if the endpoints of one edge are located between the endpoints of the other edge, and two edges cross if their endpoints alternate in the topological ordering. The minimum number s + q of queues and stacks needed for a q-queue s-stack layout is called the mixed page number. First, we determine the mixed page number of some concrete graphs. Then we investigate the mixed page number for the class of upward planar bipartite graphs before we try to find upper and lower bounds to the mixed page number of all upward planar graphs.

Kurzvortrag: Oriented Cycle Game

  • Datum: Fr, 2 Dez 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Shabi Shabani

Variable Neighborhood Search for the Solar Farm Cable Layout Problem

  • Datum: Fr, 25 Nov 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Leonie Wahl
  • Inhalt: Das Verkablungsproblem in Solarparks ist das Optimierungsproblem, für einen gegebenen Solarpark die kostengünstigste Verkablung zu finden, die zugleich verschiedene Bedingungen, wie das Einhalten von Kapazitäten der Komponenten, erfüllt. In früheren Arbeiten wurde bereits eine MILP Formulierung und eine heuristische Methode für dessen Lösung entworfen. Wir stellen eine Anwendung der Metaheuristik Variable Neighborhood Search (VNS) für das Verkablungsproblem in Solarfarmen vor. Die Performance dieser Metaheuristik wird getestet und verglichen mit der existierenden MILP Formulierung und Heuristik.
  • Datum: Fr, 11 Nov 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Nicholas Bieker, ITI Bläsius, ITI Wagner, Masterarbeit
  • Inhalt: There are many problems of geometric nature that are complete in the complexity class ER. We examine what happens to the complexity of these problems when considering hyperbolic geometry. For that, we start with line arrangements and the SimpleStretchability problem, where we are given a pseudoline arrangement and have to decide if there is a homeomorphic line arrangement. We define the hyperbolic problem version, where the line arrangements consist of hyperbolic lines, and show that the hyperbolic and Euclidean versions are equivalent. Additionally, we consider hyperbolic unit disk graphs and show that their recognition problem is ER-complete.

Integrating Ridesharing and Public Transit Routing

  • Datum: Fr, 11 Nov 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Louis Tiede

Coloring Hypergraphs Induced by Hanging Rectangles

  • Datum: Fr, 4 Nov 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Maria Nübling, ITI Wagner, Masterarbeit
  • Inhalt: tba

Theoretical Analysis of Different Dynamic Flow Variations

  • Datum: Fr, 28 Okt 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Jannik Westenfelder, ITI Bläsius, Bachelorthesis
  • Inhalt: The dynamic max flow problem is based on the static max flow problem. It extends the base problem by adding a temporal component through a travel time for arcs. We provide an overview of the hardness of different variations of this max dynamic flow problem and the needed proofs. The dynamic max flow problem is weakly NP-hard if we allow the travel times or the capacities to change at integral points in time. These results show that, in contrast to dynamic max flow problems with arcs that have a constant travel time or capacity, allowing these changes causes the problem to become NP-hard.

Forest Stack Layouts

  • Datum: Fr, 28 Okt 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Lena Scherzer, ITI Wagner, Bachelorarbeit
  • Inhalt: A stack layout of a graph consists of an ordering of the vertices s and a partition of the edges into stacks. Two edges on the same stack are not allowed to cross with respect to s, meaning that for no two edges xy and uv with s(x) < s(y) and s(u) < s(v) in the same stack we have s(x) < s(u) < s(y) < s(v) or s(u) < s(x) < s(v) < s(y). In a forest stack layout the subgraph on each stack is a forest. The minimum number of stacks needed for a stack layout of a graph is called the stack number and the minimum number of stacks needed for a forest stack layout is called the forest stack number. We determine the forest stack number of some graphs and attack the conjecture that the forest stack number of graphs might be at most one greater than the stack number for every graph. For complete graphs, complete bipartite graphs K_{m,n} with m << n, planar 3-trees and k-trees the forest stack number or the best known bound on the forest stack number is shown to be the same as the stack number. For outerplanar graphs, one more stack is needed for forest stack layouts. We also show that for every k there is a graph with stack number k that needs k + 1 stacks for a forest stack layout. Assuming some restrictions apply, we find counterexamples to the conjecture.

Shallow Edge Sets in Hypergraphs

  • Datum: Fr, 21 Okt 2022, 14:30
  • Ort: SR 131
  • Vortragende(r): Tim Planken, ITI Wagner, Masterarbeit
  • Inhalt: Let H=(V,E) be a hypergraph. A subset M of E is t-shallow if every vertex v in V has at most t incident edges that are in M. A subset M of E is hitting if every vertex v has an incident edge in M. We consider both shallow edge sets and shallow hitting edge sets. First, we give an equivalence for the existence of shallow hitting edge sets in graphs (i.e. each edge is a 2-subset of V). Moreover, we give a sufficient condition on the minimum vertex degree for the existence of t-shallow hitting edge sets in m-uniform (m-partite) hypergraphs and prove that this condition is almost tight. Then, we provide upper and lower bounds for the smallest t=t(m) such that every m-uniform regular hypergraph has a t-shallow hitting edge set. The proof of the upper bound is constructive and uses the Lovász Local Lemma. Moreover, we consider maximum size shallow edge sets and provide a lower bound for uniform regular hypergraphs and show that this lower bound is tight up to a constant factor. We also provide an explicit construction of m-uniform m-partite regular hypergraphs through projective spaces. This construction improves the lower bound on t(m) and provides an explicit construction of an m-uniform m-partite regular hypergraph with small maximum shallow edge set. Then, we show that deciding whether an m-uniform m-partite regular hypergraph has a t-shallow hitting edge set is NP-complete. Moreover, we use the existence of shallow hitting edge sets in uniform regular hypergraphs to show an upper bound for the polychromatic coloring of the union of strips.

Primal-Dual Cops and Robbers

  • Datum: Fr, 21 Okt 2022, 14:00
  • Ort: SR 131
  • Vortragende(r): Minh Tuan Ha, ITI Wagner, Bachelorarbeit
  • Inhalt: The game of cops and robbers is a pursuit and evasion game played on graphs in which both parties alternate in taking turns to move along the edges. While the cops try to catch the robber in a finite number of moves, the robber tries to evade the cops indefinitely. Contrary to the original game in which both parties move from vertex to vertex, we introduce a new variation for planar graphs with cops that advance on faces instead. In this variation, the cop number, denoted as c^*(G), specifies how many cops are required to catch the robber, that is, by occupying all faces incident to the robber's position, even if the latter plays perfectly. We first establish general lower and upper bounds on c^*(G) for planar graphs G. From there on, we consider classes of graphs such as k-regular graphs and graphs with maximum degree Delta(G) geq 5. Here we proceed by using already proven results of the original game and applying them to our setting. Furthermore, we consider the effect of subdividing edges of graphs on the cop number c^*(G). For this, we use K_4 as an example.

Solving Power Dominating Set

  • Datum: Fr, 7 Okt 2022, 15:00
  • Ort: SR 131
  • Vortragende(r): Max Göttlicher

GIRG + Stochastic Block Model

  • Datum: Fr, 7 Okt 2022, 14:00
  • Ort: SR 131
  • Vortragende(r): Florian Küfner, BA-Kurzvortrag

Sommersemester 2022

Minimizing Planar Edge Length Ratio on the Grid

  • Datum: Fr, 30 Sep 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Luca Buchholz, ITI Wagner, Bachelorarbeit
  • Inhalt: The edge length ratio of a graph drawing is defined as the ratio obtained by dividing the length of the longest edge and the shortest Euclidean distance between any two adjacent vertices. Optimizing this ratio for planar graphs drawn on a grid is the topic of the live challenge at the 30th International Symposium on Graph Drawing and Network Visualization and this thesis. The algorithm implemented takes a given initial drawing, calculated by any known algorithm drawing planar graphs on the grid, and performs a local search starting at this drawing to optimize edge length ratio.

Packing Lower Bounds for Cluster Editing

  • Datum: Fr, 30 Sep 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Maximilian Walz, ITI Bläsius, Bachelorthesis

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

  • Datum: Fr, 2 Sep 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Miriam Goetze, Probevortrag, ESA 2022
  • Inhalt: It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an n-vertex planar graph, augments this graph in O(n^2) steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized-Antifactor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.
  • Datum: Fr, 26 Aug 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Nicholas Bieker, ITI Bläsius, ITI Wagner
  • Inhalt: Kurzvortrag zur Masterarbeit.

Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time

  • Datum: Fr, 26 Aug 2022, 14:00
  • Ort: SR 301 and https://kit-lecture.zoom.us/j/63982875014?pwd=MVVVK1N1MDdpUFgzKzBnTU96L0Rmdz09
  • Vortragende(r): Chris, IPEC22 rehearsal
  • Inhalt: Given an undirected graph, the task in CLUSTER EDITING is to insert and delete a minimum number of edges to obtain a cluster graph, that is, a disjoint union of cliques. In the weighted variant each vertex pair comes with a weight and the edge modifications have to be of minimum overall weight. In this work, we provide the first polynomial-time algorithm to apply the following data reduction rule of Böcker et al. [Algorithmica, 2011] for WEIGHTED CLUSTER EDITING: For a graph~$G = (V,E)$, merge a vertex set~$S subseteq V$ into a single vertex if the minimum cut of~$G[S]$ is at least the combined cost of inserting all missing edges within~$G[S]$ plus the cost of cutting all edges from~$S$ to the rest of the graph. Complementing our theoretical findings, we experimentally demonstrate the effectiveness of the data reduction rule, shrinking real-world test instances from the PACE Challenge 2021 by around 24,\% while previous heuristic implementations of the data reduction rule only achieve 8,\%.

Oh the Connection Between Exactly Solving and Approximating Vertex Cover

  • Datum: Fr, 19 Aug 2022, 14:45
  • Ort: SR 301
  • Vortragende(r): Carina Weber

Homogenizing Heterogeneous Graphs with Underlying Geometry

  • Datum: Fr, 19 Aug 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Nils Schewe

Algorithm Comparison for Autonomous Mobile Robots Scheduling

  • Datum: Fr, 19 Aug 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Jakob Wagenblatt, ITI Bläsius & FZI, Masterthesis
  • Inhalt: With the advent of Industry 4.0 and increasing automation, the importance of autonomous mobile robots (AMR) for transporting goods in intralogistics is growing. Consequently, this has given rise to the development of new centralized and decentralized methods for scheduling and routing these robots. However, there is a lack of comparison between the different algorithms, which moreover often do not model important features of the real world. Therefore, we develop a discrete-event simulation framework allowing easy comparison of different scheduling algorithms for the Electric Multi-Agent Pickup and Delivery (EMAPD) problem by finding a general basis for modeling instances. The EMAPD is an online problem in which delivery tasks arrive continuously and have to be assigned to AMRs. Its solutions consists of collision-free routes that fulfill these tasks while considering battery constraints, charging as necessary and minimizing tardiness. We evaluate the performance of seven different schedulers experimentally on ten different scenarios varying in layout, size, number of robots and system load. Our experiments show that the performance of the schedulers varies wildly, depending on the scenario and especially the system load. We attribute this in part to the charging strategy used as a simple rule-based scheduler implemented for reference with a different charging strategy sometimes performs best. Overall, we rate an auction-based scheduler punishing tardiness best. On average, it produces good results and performs efficiently.

Homogenizing Heterogeneous Graphs with Underlying Geometry

  • Datum: Fr, 12 Aug 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Nils Schewe

Efficient Long-Haul Truck Driver Routing

  • Datum: Fr, 12 Aug 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Max Oesterle, ITI Wagner, Masterarbeit
  • Inhalt: Truck drivers on long-haul journeys must take breaks and rest periods due to regulatory constraints. Most regulations require the driver to take breaks of a certain minimum duration after having accumulated a maximum allowed driving time. At the same time, a break or rest period must be scheduled at a parking location which is suitable for a truck. This leads to the challenge of choosing parking locations which minimize the increase in travel time caused by the detour to the parking location, and finding the best route between start, parking locations, and the destination. The travel time is the sum of the pure driving time and the accumulated break time on the route. We call this problem the Long-Haul Truck Driver Routing Problem. We use a simplified model to abstract from real-world regulations. The problem of finding routes with the shortest travel time that comply with our model of regulations is called the Truck Driver Routing Problem (TDRP). We present a label-based algorithm which is able to solve the TDRP. The algorithm is further improved using a goal-directed search, a bidirectional search, a core contraction hierarchy, or combinations of these. The goal-directed core CH algorithm achieves average running times on a European road network of about 10 ms which allows the application of our work in practical applications.

Kurzvortrag: Coloring Hypergraphs Induced by Hanging Rectangles

  • Datum: Fr, 29 Jul 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Maria Nübling
  • Inhalt: Kurzvortrag zu Masterarbeit

Entwicklung eines Exakten Algorithmus für das Directed Feedback Vertex Set Problem

  • Datum: Fr, 29 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Ruben Götz, ITI Bläsius, Bachelorthesis
  • Inhalt: In dieser Arbeit wurde ein Algorithmus zum Lösen des Directed Feedback Vertex Set Problems entwickelt. Der Algorithmus folgt einem Branch&Bound Ansatz. Den Hauptbestandteil dieser Arbeit bildet die Reduktion von Probleminstanzen. Hierfür werden 10 Reduktionsregeln vorgestellt. Auch die Implementierung des Algorithmus wird in dieser Arbeit diskutiert. Der hier behandelte Algorithmus wurde in der Programmiersprache C++ implementiert und steht öffentlich zur Verfügung. Die Testergebnisse der Implementierung wurden in dieser Arbeit zusammengefasst.

A Branch-And-Bound Algorithm for Cluster Editing (SEA22 Testrun)

  • Datum: Fr, 22 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Chris
  • Inhalt: Read the paper if you are interested. https://doi.org/10.4230/LIPIcs.SEA.2022.13 Zoom Link: https://kit-lecture.zoom.us/j/63982875014?pwd=MVVVK1N1MDdpUFgzKzBnTU96L0Rmdz09

Kurzvortrag: Random Minimum Spanning Trees in the Hyperbolic Plane

  • Datum: Fr, 15 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Yavor Lakov

About the Analysis of Algorithms on Networks with Underlying Hyperbolic Geometry

  • Datum: Fr, 15 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Maximilian Katzmann
  • Inhalt: Many complex systems that we encounter in the world can be formalized using networks. Consequently, they have been in the focus of computer science for decades, where algorithms are developed to understand and utilize these systems. Surprisingly, our theoretical understanding of these algorithms and their behavior in practice often diverge significantly. In fact, they tend to perform much better on real-world networks than one would expect when considering the theoretical worst-case bounds. One way of capturing this discrepancy is the average-case analysis, where the idea is to acknowledge the differences between practical and worst-case instances by focusing on networks whose properties match those of real graphs. Recent observations indicate that good representations of real-world networks are obtained by assuming that a network has an underlying hyperbolic geometry. In this talk I give an overview of the findings in my thesis, where it was demonstrated that the connection between networks and hyperbolic space can be utilized as a powerful tool for average-case analysis. To this end, I will give an introduction to networks with underlying hyperbolic geometry and go through an example where the model guided us towards an algorithm that solves a hard problem more efficiently in practice.

On the External Validity of Average-Case Analyses of Graph Algorithms

  • Datum: Fr, 8 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Thomas Bläsius
  • Inhalt: also via zoom: https://kit-lecture.zoom.us/j/65303658822?pwd=UGdSbmdoRUQydktad0NwL09GTVhpdz09 The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.

Point-of-Interest Queries in Public Transit Networks

  • Datum: Fr, 1 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): John Gelhausen, Masterarbeit
  • Inhalt: We study the problem of finding the k-nearest POIs in pure public transit and multi-modal networks. For the multi-modal networks, we combine a public transit network with a non-schedule-based mode of transport. Given a departure time and a single source vertex, we want to find the k closest vertices in a set of targets, optimizing the arrival time. Our solution for pure public transit networks is a combination of two state-of-the-art algorithms: ACSA, which enables efficient one-to-one queries, and CRP, which enables efficient one-to-many queries in road networks. Our solution for multi-modal networks, k-UP-CSA, is a combination of ACSA and ULTRA-PHAST, which enables efficient one-to-many queries in multi-modal networks. We examine the performance of both our extension to ACSA and k-UP-CSA on the networks of London, Switzerland and Germany. Both algorithms achieve high speed-ups on country-sized public transit networks, such as Switzerland and Germany. On urban-sized public transit networks, our algorithms are still faster than the baseline algorithms, however the speed-up we achieve is less impressive compared to country-sized public transit networks.

Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks

  • Datum: Fr, 24 Jun 2022, 14:15
  • Ort: SR 301
  • Vortragende(r): Marcus
  • Inhalt: A common technique to speed up shortest path queries in graphs is to use a bidirectional search, i.e., performing a forward search from the start and a backwards search from the destination until a common vertex on a shortest path is found. In practice, this has a tremendous impact on the performance on some real-world networks, while it only seems to save a constant factor on other types of networks. Even though finding shortest paths is a ubiquitous problem, there are only few studies attempting to understand the apparently asymptotic speedups on some networks, using average case analysis on certain models for real-world networks. In this paper we give a new perspective on this, by analyzing deterministic properties that permit theoretical analysis and that can easily be checked on any particular instance. We prove that these parameters imply sublinear running time for the bidirectional BFS in several regimes, some of which are tight. Moreover, we perform experiments on a large set of real-world networks showing that our parameters capture the concept of practical running time well.

Variable Neighborhood Search for the Solar Farm Cable Layout Problem

  • Datum: Fr, 24 Jun 2022, 14:00
  • Ort: 315
  • Vortragende(r): Leonie Wahl
  • Inhalt: Leonie is giving a short presentation on her Bachelor's thesis.

Variable Neighborhood Search for the Solar Farm Cable Layout Problem

  • Datum: Di, 21 Jun 2022, 10:30
  • Ort: tba
  • Vortragende(r): Leonie Wahl
  • Inhalt: Short presentation on Leonie's Bachelor's thesis

Kurzvortrag: Forest Stack Layouts

  • Datum: Di, 21 Jun 2022, 10:15
  • Ort: tba
  • Vortragende(r): Lena Scherzer, ITI Wagner, Bachelorarbeit

Shallow Hitting Sets

  • Datum: Di, 21 Jun 2022, 10:00
  • Ort: 315
  • Vortragende(r): Tim Planken

Anzahl inklusionsmaximaler Cliquen in geometrischen Zufallsgraphen

  • Datum: Fr, 3 Jun 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Niko Lemke, ITI Bläsius, BA Abschlussvortrag
  • Inhalt: Krankheitsbedingt erneut verschoben (auf den 3.6.)

Kurzvortrag: Packing Lower Bounds for Cluster Editing

  • Datum: Fr, 20 Mai 2022, 14:15
  • Ort: SR 301
  • Vortragende(r): Maximilian Walz, ITI Bläsius, Bachelorthesis

Kurzvortrag: Theoretical Analysis of Different Dynamic Flow Variations

  • Datum: Fr, 20 Mai 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Jannik Westenfelder, ITI Bläsius, Bachelorthesis

Interval Colorings on Graphs

  • Datum: Fr, 6 Mai 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Michael Zheng, ITI Wagner; Bachelor Thesis
  • Inhalt: A graph G is called interval colorable if there is an assignment of integers to its edges such that each vertex is incident to edges colored by a set of consecutive integers and there are no two adjacent edges of the same color. This notion was motivated by the problem of finding compact school timetables, i.e. timetables such that the lectures of each teacher and each class are scheduled in consecutive periods. First, we survey some results in the study of interval colorability and related topics. In particular, we focus our attention on current results on the interval thickness, a relaxation of interval colorability where we want to edge-decompose the graph into as few interval colorable subgraphs as possible. After that, we will present a new upper bound on the interval thickness using a powerful tool in extremal graph theory and then show that the spectrum, which we define as the set of all positive integers t such that there is an interval coloring using the integers 1 to t, can have arbitrarily many and arbitrarily large gaps.

Minimum Linear Arrangement revisited

  • Datum: Fr, 22 Apr 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Michael Zündorf, MA Vortrag

Extending, Recombining and Evaluating Contraction Hierarchy-based Many-to-Many Shortest Path Algorithms

  • Datum: Di, 12 Apr 2022, 13:00
  • Ort: SR 301
  • Vortragende(r): Theo Wieland, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

ULTRA on Public Transit Networks with Limited Transfers

  • Datum: Fr, 8 Apr 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Alexander Vogel, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Public Transit Routing with Real-Time Updates

  • Datum: Fr, 8 Apr 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Daniel Zhang, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

The Planar Graph Grabbing Game

  • Datum: Di, 5 Apr 2022, 13:30
  • Ort: SR 301
  • Vortragende(r): Benedikt Hahn, ITI Wagner; Bachelor Thesis
  • Inhalt: In this work we introduce a new game on graphs called “The planar graph grabbing game”. The game is played on a plane graph with vertices weighted 0 and 1. Vertices with weight 1 are called cherries. Two players – Alice and Bob starting with Alice – take turns removing single vertices (and in doing so their incident edges) from the outer face of the remaining graph. The game ends when no vertices are left and the player who obtained the most weight wins. We call an instance Bob-dominant when Bob is able to obtain all cherries on the instance, no matter which strategy Alice follows. First, we show that there are Bob-dominant instances with arbitrarily many cherries. We also prove that there are even 4-connected triangulated Bob-dominant instances with arbitrarily many cherries. We then give examples for 4-connected triangulated Bob-dominant instances of odd size with up to six cherries and prove that no such graphs can exist for seven or more cherries. Finally, we briefly pursue the question what share of cherries Alice is guaranteed to get on odd 4-connected triangulated instances with “many” cherries.

Cooperative Route Planning on Time-Dependent Road Networks

  • Datum: Di, 5 Apr 2022, 13:00
  • Ort: SR 301
  • Vortragende(r): Nils Werner, ITI Wagner; Master Thesis
  • Inhalt: TBA

On Hyperbolic Unit Disk Graphs

  • Datum: Fr, 1 Apr 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Emil Dohse, ITI Wagner; Master Thesis
  • Inhalt: Wird auch bei Zoom übertragen: https://kit-lecture.zoom.us/j/65303658822?pwd=UGdSbmdoRUQydktad0NwL09GTVhpdz09