Forschungsseminar
Wintersemester 2025
On Improper Colorings of 1-Planar Graphs
- Datum: Fri, 13 Feb 2026, 14:15
- Ort: SR 301
- Vortragende(r): Arian Küpper, Bsc Ueckerdt -- Short Presentation
Reconfiguration of graphs under edge additions and deletions
- Datum: Fri, 13 Feb 2026, 14:00
- Ort: SR 301
- Vortragende(r): Lennart Blumenthal, Bsc thesis Ueckerdt -- Short Presentation
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
- Datum: Tue, 10 Feb 2026, 14:30
- Ort: SR 301
- Vortragende(r): Mong-Jen Kao
Average Case Fine Grained Complexity of Dominating Set
- Datum: Fri, 30 Jan 2026, 14:00
- Ort: SR 301
- Vortragende(r): Leonie Wahl
- Inhalt: Master Thesis Introductory Talk, supervised by Sebastian Angrick and Marvin Künnemann
Now you're thinking with portals: Graph reconfiguration on the torus
- Datum: Fri, 23 Jan 2026, 14:30
- Ort: SR 301
- Vortragende(r): Anouk Sommer
- Inhalt: Interim Presentation for Praxis der Forschung, supervised by Miriam Goetze and Torsten Ueckerdt
Algorithms on Compressed Graphs
- Datum: Fri, 23 Jan 2026, 14:20
- Ort: SR 301
- Vortragende(r): Marko Pejic
- Inhalt: Interim Presentation for Praxis der Forschung, supervised by Mirza Redzic and Mavin Künnemann
KD-Tree goes brrr: Spatial Indices for Weigthed Space
- Datum: Fri, 23 Jan 2026, 14:00
- Ort: SR 301
- Vortragende(r): Tobias Kempf and Dennis Kobert
- Inhalt: Interim Presentation for Praxis der Forschung, supervised by Jean-Pierre von der Heydt and Thomas Bläsius
Graph Coverings
- Datum: Fri, 16 Jan 2026, 14:00
- Ort: SR 301
- Vortragende(r): Lucas Schwebler
- Inhalt: B.Sc. Short presentation (supervised by Miriam Goetze)
Pattern-Avoiding Vertex Orders with SAT
- Datum: Fri, 9 Jan 2026, 14:00
- Ort: SR 301
- Vortragende(r): Jonathan Dransfeld, MA Kurzvortrag
B.Sc. Short Presentation: Algorithms on Strong Products
- Datum: Fri, 19 Dec 2025, 14:00
- Ort: SR 301
- Vortragende(r): Manuel Rapp
Are Faster Parallelized Max-Flow Algorithms Possible
- Datum: Tue, 16 Dec 2025, 14:30
- Ort: SR 301
- Vortragende(r): Jonas Sauer
Fine-grained Complexity of Verifying Properties of Algebraic Structures
- Datum: Fri, 12 Dec 2025, 14:30
- Ort: SR 301
- Vortragende(r): Jens Grabmaier
M.Sc. thesis talk: Fine-grained Complexity of Generalized Domination Problems
- Datum: Fri, 12 Dec 2025, 14:00
- Ort: SR 301
- Vortragende(r): Elly Schmidt
Parameterized Complexity of Zero Forcing and its Variants
- Datum: Fri, 12 Dec 2025, 13:30
- Ort: BR 315
- Vortragende(r): Lennard Hofmann
Comparing Geometric Embeddings of Graphs
- Datum: Fri, 5 Dec 2025, 14:30
- Ort: SR 301
- Vortragende(r): Linda Staerke, B. Sc. Abschlussvortrag
On Computing Clique-Partitioned Treewidth
- Datum: Fri, 5 Dec 2025, 14:00
- Ort: SR 301
- Vortragende(r): Sven Geißler, M.Sc. Intro Talk
The Cograph Cover Number: Bounds and Constructions
- Datum: Fri, 21 Nov 2025, 14:00
- Ort: SR 301
- Vortragende(r): Tommy Riediger, Bsc thesis Ueckerdt
- Inhalt: Cographs are the graphs that contain no induced P_4. They possess rich structural properties and serve as a basis for efficient algorithms. In this talk, I will discuss the cograph cover number f(G), the minimum number of cographs on V(G) whose edge sets together cover E(G). After a short overview and examples for special graph classes, I will focus on two results: a characterization of k-partite cographs via a cotree coloring rule, and a lower bound of Omega(n/log n) on f(G(n,1/2)) for random graphs.
The Complexity of the Flow-weighted Layered Minimal Euclidean Capacitated Steiner Tree Problem
- Datum: Tue, 18 Nov 2025, 14:30
- Ort: SR 301
- Vortragende(r): Wendy Yi
Complexity of Zero Forcing
- Datum: Fri, 14 Nov 2025, 14:15
- Ort: SR 301
- Vortragende(r): Tim Wellenreich, BA Abschlussvortrag
A lower bound on MMCS (BSc short talk)
- Datum: Fri, 14 Nov 2025, 14:00
- Ort: SR 301
- Vortragende(r): Bennet Hörmann
Traveling the W-hierarchy with l-round Power Dominating Set
- Datum: Tue, 11 Nov 2025, 14:30
- Ort: SR 301
- Vortragende(r): Max Göttlicher
- Inhalt: The Power Domating Set Problem is a graph problem that asks for the smallest vertex set that observes the whole graph by two rules. By the first rule the selected vertices and their neighbours are observed, akin to the Dominating Set Problem. By the second rule, if an observed vertex has only one unobserved neighbour, that neighbour becomes observed, too. This is applied iteratively until no such vertices remain. It has long been known that by its relation to Dominating Set PDS is W[2]-hard when parameterized by the solution size and more recently has been shown to be in fact W[P]-hard. We extend these result and show that limiting the number of propagating steps places the problem in different levels of the W-hierarchy. In particular, we show that l-round PDS is in W[2l].
On a Comparison of Disk and Weighted Embeddings
- Datum: Fri, 7 Nov 2025, 14:30
- Ort: SR 301
- Vortragende(r): Malik
- Inhalt: Geometric graph models are useful for analysis of real-world graph behavior and to obtain low-dimensional representations. One such model are Geometric Inhomogeneous Random Graphs (GIRGs). In the threshold case a d-dimensional weighted graph, i.e., non-random GIRG, is given by a mapping from vertices v to points p_v in R^d and weights w_v > 0 s.t. u != v are adjacent if and only if ||p_u-p_v|| <= w_u * w_v. This is similar to the well-known model of disk graphs where vertices are adjacent if and only if ||p_u-p_v|| <= r_u + r_v, i.e., if the closed disks with center point p and radius r >= 0 intersect. Our goal is to compare both models and see if and where they differ.
Partition of Time-Dependent Routes into Fixed-Size Vehicles
- Datum: Fri, 7 Nov 2025, 14:00
- Ort: SR 301
- Vortragende(r): Marco Rieger
- Inhalt: As demand for private traffic increases, roads are increasingly congested by vehicles serving only a single person. However, multiple people traveling along similar routes, could instead use a shared vehicle for their trip, which motivates the Vehicle Sharing Fixed Routes Problem in a road network, for which we introduce a problem formulation. In this problem all vehicles have the same capacity and no transfers between vehicles are allowed. All passengers want to travel along a fixed route, and every vehicle used is owned by a passenger who uses it from their origin to their destination. Along their route, they can fill the vehicle’s capacity with other passengers. We show that finding an assignment that minimizes the total vehicle operation time is NP hard, even if we restrict the road network to a simple directed path with unit distance edges. Afterwards, we consider the scenario in which there is only one driver who can transport other passengers. We present an algorithm that solves this scenario in O(nC log(n)) for an arbitrary vehicle size C>=2 by reducing it to Maximal Weight Fixed Interval Scheduling.
Hyperbolic Sphericity
- Datum: Fri, 31 Oct 2025, 14:15
- Ort: SR 301
- Vortragende(r): Jean-Pierre von der Heydt
Faster CCH Queries
- Datum: Fri, 31 Oct 2025, 14:00
- Ort: SR 301
- Vortragende(r): Julius Schömer
Graphs in Hyperbolic Geometry
- Datum: Wed, 29 Oct 2025, 14:00
- Ort: SR 301
- Vortragende(r): Thomas Bläsius
Discovering Functional Dependencies through Hitting Set Enumeration
- Datum: Tue, 21 Oct 2025, 13:00
- Ort: SR 236
- Vortragende(r): Martin Schirneck
- Inhalt: A functional dependency (FD) in a relational database is a pair X -> A consisting of a set of columns X and another column A such that knowing the value combination appearing in X lets us infer the value of A. The FD discovery problem is the task of listing all functional dependencies of a given database. This talk discusses the close conncection between FD discovery and the enumeration of hitting sets in hypergraphs. We will also highlight a few open questions in the area. This is joint work with Tobias Bleifuß, Thorsten Papenbrock, Thomas Bläsius, and Felix Naumann.
Customizable Contraction Hierarchies on Hyperbolic Graphs
- Datum: Fri, 17 Oct 2025, 14:00
- Ort: SR 301
- Vortragende(r): Henning Lindemann
Sommersemester 2025
Complexity of the Constrained Layer Tree problem
- Datum: Tue, 30 Sep 2025, 13:00
- Ort: SR 301
- Vortragende(r): Tamara Buchler, BA Abschlusspräsentation
Algorithmic and structural properties of subgraphs of strong grids
- Datum: Fri, 26 Sep 2025, 15:00
- Ort: SR 301
- Vortragende(r): Jan Diester, Abschlussvortrag BSc-Arbeit Ueckerdt
Comparing Variants of Product Structure
- Datum: Fri, 26 Sep 2025, 14:30
- Ort: SR 301
- Vortragende(r): Lena Scherzer (M.Sc. Abschlussvortrag)
- Inhalt: A graph class G has geodesic structure if there exists a constant k such that every G’ in G has a partition P of V(G’) into geodesics such that G’/P has treewidth at most k. A graph class G has product structure if there exists a constant k such that every G’ in G has a layering L and a partition P of layered width 1 such that G’/P has treewidth at most k. Each set in a partition P of layered width 1 is allowed to contain at most one vertex in each layer in L. The topic of my thesis is to investigate the relationships between these two variants and other related concepts. We show that product structure does not imply geodesic structure. For geodesic structure with k=1 we show that it implies product structure. We also compare other variants of product structure and investigate the relationships between bounded layered treewidth, Baker treewidth and bounded local treewidth, which are all necessary conditions for product structure. Lastly, we show that some known results for product structure also hold for geodesic structure. For example, linear local treewidth is necessary for geodesic structure and calculating the geodesic treewidth is NP-hard. However, contrary to product structure, for graphs with treewidth 2, calculating the geodesic treewidth is possible in polynomial time.
Upward k-Planarity
- Datum: Fri, 26 Sep 2025, 14:00
- Ort: SR 301
- Vortragende(r): Franka Fockel (B.Sc. Abschlussvortrag)
- Inhalt: A directed acyclic graph (DAG) G is called upward k-planar if there exists an embedding of G in the plane such that every edge is a y-monotone Jordan curve and is crossed at most k times. The upward local crossing number of a graph G is the smallest integer k such that G is upward k-planar. It is known that the upward local crossing number of G is at most bw(G) squared, where bw(G) denotes the bandwidth of G. We establish improved bounds in the case where G is the Cartesian product of two directed input graphs. For two oriented paths P_1 and P_2 of lengths n_1 and n_2, respectively, we show, by developing suitable embedding techniques, that the upward local crossing number of the Cartesian product of P_1 and P_2 lies in O (square root of the minimum of n_1 and n_2). Moreover, for two DAGs G_1 and G_2, we prove that the upward local crossing number of the Cartesian product of these graphs lies in O(cube of the maximum of bw(G_1) and bw(G_2)). A partially ordered set (poset) P is called upward k-planar if its Hasse diagram is upward k-planar. We show that there exists no function that bounds the dimension of a poset in terms of its upward local crossing number, nor vice versa.
B.Sc. Vortrag: Improving Algorithms for the Discrete Fr�chet Distance under Translation
- Datum: Fri, 19 Sep 2025, 14:00
- Ort: SR 301
- Vortragende(r): Paul Gauer
PdF project proposal: Fine-grained Complexity of Algorithmic Primitives on Compressed Graphs
- Datum: Tue, 16 Sep 2025, 13:30
- Ort: SR 301
- Vortragende(r): Marko Pejic
Investigating the Influence of Sparsity for Boolean Constraint Satisfaction
- Datum: Fri, 5 Sep 2025, 14:30
- Ort: SR 301
- Vortragende(r): Timo Fritsch, Master Thesis
On the Attacking Cop Number of a Graph
- Datum: Fri, 22 Aug 2025, 14:00
- Ort: SR 301
- Vortragende(r): Florian Brendle, Abschlussvortrag Bsc-Arbeit Ueckerdt
- Inhalt: We consider the game of Cops and Attacking Robber, a variant of the game of Cops and Robber in which at each robber turn, the robber may eliminate (at most) one cop by moving onto it. The number of cops that is required to capture the robber in a game of Cops and (Attacking) Robber in a graph G is denoted by c(G) and cc(G) respectively. Among other results, we prove a conjecture by A. Clow, M. A. Huggan, and M. Messinger that there are connected graphs G with arbitrarily large cop numbers satisfying cc(G) = 2 c(G).
Counting Polyominoes, Revisited
- Datum: Mon, 18 Aug 2025, 11:00
- Ort: SR 301
- Vortragende(r): Gill Barequet, The Technion -- Israel Inst. of Technology
- Inhalt: A polyomino is an edge-connected set of squares on the square lattice. We improve Jensen's algorithm for counting polyominoes by considering bounding boxes on the square lattice rotated by 45° instead of on the regular unrotated lattice. This allows us to extend significantly the count of polyominoes from 56 to 70 terms.
Shortcut Sets: Reducing the Diameter of Directed Graphs
- Datum: Fri, 15 Aug 2025, 14:10
- Ort: SR 301
- Vortragende(r): Ben Bals
Bc Kurzvortrag - Shared Vehicle Assignment with Stop Costs
- Datum: Fri, 15 Aug 2025, 14:00
- Ort: SR 301
- Vortragende(r): Yannik Weiser
Complexity of Verifying Algebraic Identities
- Datum: Tue, 12 Aug 2025, 13:00
- Ort: SR 301
- Vortragende(r): Mirza Redzic
Understanding Small Separators in Road Networks
- Datum: Fri, 11 Jul 2025, 14:00
- Ort: SR 301
- Vortragende(r): Samuel Born
Algorithmic Lovasz Local Lemma and Entropy Compression
- Datum: Fri, 4 Jul 2025, 14:00
- Ort: SR 301
- Vortragende(r): Kolja Kühn
Deterministic Verification and Correction Algorithms for Matrix Products
- Datum: Fri, 27 Jun 2025, 14:10
- Ort: SR 301
- Vortragende(r): Maximilian Limmer
- Inhalt: B.Sc. thesis final presentation
Short Presentation: Improving Algorithms for the Fr�chet distance under Translation
- Datum: Fri, 27 Jun 2025, 14:00
- Ort: SR 301
- Vortragende(r): Paul Gauer
tba
- Datum: Tue, 24 Jun 2025, 13:00
- Ort: SR 301
- Vortragende(r): Torsten Ueckerdt
Partition of Time-Dependent Routes into Fixed-Size Vehicles
- Datum: Fri, 20 Jun 2025, 15:00
- Ort: SR 301
- Vortragende(r): Marco Rieger, Kurzvortrag
Transit Planning Utilizing Ride Sharing Techniques
- Datum: Fri, 20 Jun 2025, 14:30
- Ort: SR 301
- Vortragende(r): Maximilian Walz
PdF SotA presentation: Fine-grained complexity on compressed graphs
- Datum: Fri, 20 Jun 2025, 14:00
- Ort: SR 301
- Vortragende(r): Marko Pejic
Structure and Independence in Hyperbolic Uniform Disk Graphs
- Datum: Tue, 17 Jun 2025, 13:15
- Ort: SR 301
- Vortragende(r): Marcus Wilhelm
- Inhalt: This talk has already been given by Thomas - this is now the conference version to be held in a couple of weeks.
Short presentation (M.Sc. thesis): Fine-grained Complexity of Generalized Domination Problems
- Datum: Tue, 17 Jun 2025, 13:00
- Ort: SR 301
- Vortragende(r): Elly Schmidt
Complexity of the Constrained Layer Tree Problem
- Datum: Fri, 13 Jun 2025, 14:00
- Ort: SR 301
- Vortragende(r): Tamara Buchler, BA Kurzvortrag
Complexity of Zero Forcing
- Datum: Fri, 6 Jun 2025, 15:00
- Ort: SR 301
- Vortragende(r): Tim Wellenreich, BA Kurzvortrag
Dot-Product Dimension
- Datum: Fri, 6 Jun 2025, 14:45
- Ort: SR 301
- Vortragende(r): Linda Staerke, BA-Kurzvortrag
Upward k-Planarity
- Datum: Fri, 6 Jun 2025, 14:30
- Ort: SR 301
- Vortragende(r): Franka Fockel, Kurzpräsentation
- Inhalt: Die Einbettung eines Graphen G wird als upward k-planar bezeichnet, wenn jede Kante als in y-Richtung monoton wachsende Jordan Kurve eingezeichnet ist und höchstens k-mal von anderen Kanten gekreuzt wird.Das kleinste k, für das der Graph G eine upward k-planare Einbettung besitzt, wird als upward local crossing number von G bezeichnet.In der geplanten Bachelorarbeit soll untersucht werden, ob sich für bestimmte Graphklassen, namentlich Posets und Kartesische Produkte von upward-k-planaren Graphen, effektive Schranken für die upward local crossing number bestimmen lassen. Als erste Erkenntnis lässt sich festhalten, dass die upward local crossing number des Kartesischen Produkts von zwei Pfaden mit beliebiger Orientierung in O(sqrt(n)) liegt. betreut von Laura und Samuel
Combining Vertex Ordering
- Datum: Fri, 6 Jun 2025, 14:00
- Ort: SR 301
- Vortragende(r): Moritz Bär, (Msc-thesis Ueckerdt)
Prep Talk: Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
- Datum: Tue, 3 Jun 2025, 13:00
- Ort: SR 301
- Vortragende(r): Anouk Sommer
Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs
- Datum: Wed, 28 May 2025, 13:00
- Ort: SR 301
- Vortragende(r): Marco D'Elia
- Inhalt: In this paper, we study the following question. Let $mathcal G$ be a family of planar graphs and let $kgeq 3$ be an integer. What is the largest value $f_k(n)$ such that every $n$-vertex graph in $mathcal G$ has an induced subgraph with degree at most $k$ and with $f_k(n)$ vertices? Similar questions, in which one seeks a large induced forest, or a large induced linear forest, or a large induced $d$-degenerate graph, rather than a large induced graph of bounded degree, have been studied for decades and have given rise to some of the most fascinating and elusive conjectures in Graph Theory. We tackle our problem when~$mathcal G$ is the class of the outerplanar graphs or the class of the planar graphs. In both cases, we provide upper and lower bounds on the value of $f_k(n)$. For example, we prove that every $n$-vertex planar graph has an induced subgraph with degree at most $3$ and with $frac{5n}{13}>0.384n$ vertices, and that there exist $n$-vertex planar graphs whose largest induced subgraph with degree at most $3$ has $frac{4n}{7}+O(1)<0.572n+O(1)$ vertices.
Short Presentation: Product Structure vs Geodesic Structure
- Datum: Fri, 23 May 2025, 14:00
- Ort: SR 301
- Vortragende(r): Lena Scherzer
- Inhalt: A graph class has geodesic structure if there exists a constant k such that every graph G in the class has a partition P of G into geodesics such that the quotient G/P has treewidth at most k. A graph class has product structure if there exists a constant k such that every graph G in the class has a partition P of layered width 1 such that the quotient G/P has treewidth at most k. We investigate the relation between these two quite similar sounding concepts that have historically also been used in a similar context. Currently we suspect that there are in fact some fundamental differences that result in neither property implying the other. Supervised by Laura and Samuel
Proseminar Kurzvortrag: (Wang) Tilings
- Datum: Fri, 23 May 2025, 13:45
- Ort: SR 301
- Vortragende(r): Joshua Blömer
- Inhalt: Vortragssprache: Deutsch
(Multivariate) k-SUM as a barrier to succinct computation
- Datum: Tue, 13 May 2025, 13:00
- Ort: SR 301
- Vortragende(r): Geri Gokaj
A Metaheuristic for the FLaMECaST Problem
- Datum: Fri, 9 May 2025, 14:00
- Ort: SR 301
- Vortragende(r): Simon Kienle, BA Abschlussvortrag
3-Linear Degeneracy Testing
- Datum: Tue, 6 May 2025, 14:00
- Ort: 50.28 (InformatiKom) Seminarraum 1
- Vortragende(r): Marvin Künnemann
- Inhalt: https://dl.acm.org/doi/abs/10.1145/3357713.3384275 https://arxiv.org/abs/2001.01289
Odd chromatic number of circle graphs and beyond
- Datum: Wed, 30 Apr 2025, 13:00
- Ort: SR 301
- Vortragende(r): Thorsten Ueckert
- Inhalt: An odd coloring of a graph G is a proper vertex coloring so that in the neighborhood of each non-isolated vertex v of G, there exists a color which appears on an odd number of vertices in the open neighborhood of v. The odd chromatic number X_odd(G) is the minimum number of colors in an odd coloring of G. A graph class is X_odd-bounded if the odd chromatic number can be bounded in terms of the clique number in that class. That is, tthere exists a function f such that every graph G in that class with no K_t has odd chromatic number at most f(t). We prove that the class of circle graphs (intersection graphs of chords of a circle) is X_odd-bounded -and, if time allows, we discuss some far-reaching generalizations of this result.
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
- Datum: Wed, 16 Apr 2025, 14:00
- Ort: SR 301
- Vortragende(r): Julian Stieß
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
- Datum: Tue, 8 Apr 2025, 13:00
- Ort: SR 301
- Vortragende(r): Martin Schirneck (University of Vienna)
- Inhalt: This talk is about the design of fault-tolerant data structures that can report graph parameters like distances or connectivity even after some edges of the underlying graph G have failed. An important tool in the area are (L,f)-replacement path coverings (RPCs). These are families of subgraphs of G that guarantee the following property for every set F of at most f edge failures and every pair of vertices s and t: If there is a shortest s-t-path in the graph G-F that has at most L edges, then at least one subgraph in the RPC contains no edge of F but all edges of this replacement path. We present a new construction of (L,f)-replacement path coverings whose parameters improve over previous works by Weimann and Yuster [FOCS 2010] as well as Karthik and Parter [SODA 2021]. We then briefly discuss how this can be used to construct fault-tolerant data structures for shortest paths and even for NP-hard problems like k-Path and k-Clique. The talk is based on joined work with Davide Bilò, Keerti Choudhary, Sarel Cohen, and Tobias Friedrich that appeared at AAAI 2025.
Synergistic Traffic Assignment
- Datum: Wed, 2 Apr 2025, 14:00
- Ort: SR 301
- Vortragende(r): Adrian Feilhauer
Wintersemester 2024
BA Abschlussvortrag - Degree Independent Weights for Weighted Embeddings
- Datum: Fri, 28 Mar 2025, 15:30
- Ort: SR 301
- Vortragende(r): Karl Bernhard
Embedding into Graph Products: Computational Complexity and Algorithms
- Datum: Fri, 28 Mar 2025, 15:00
- Ort: SR 301
- Vortragende(r): Antonia Heiming, Bachelor Thesis Defense (talk in German)
- Inhalt: Embedding trees into product graphs has already been investigated. In this thesis, we explore the computational complexity of embedding graphs, particularly trees, into products of two paths and a clique, considering both the Cartesian and the strong products. The complexity strongly depends on the lengths of the paths involved. We show that deciding whether a tree can be embedded into the product of two paths, where one path is infinite and combined with a clique of arbitrary size, is NP-hard. However, embedding a caterpillar into such a structure can be decided in linear time. Additionally, we demonstrate that embedding a graph into the strong product of an infinite path and a path of fixed length is achievable in polynomial time. An algorithm is provided to embed a tree into the strong product of an infinite path and a clique $K_2$, solving this problem in linear time.
Die Auswirkungen neuer Kanten auf den CCH-Algorithmus
- Datum: Fri, 28 Mar 2025, 14:30
- Ort: SR 301
- Vortragende(r): Benedikt Müller, BA Vortrag (Talk in German)
Solving Power Domination with Bounded Propagation
- Datum: Fri, 28 Mar 2025, 14:00
- Ort: SR 301
- Vortragende(r): Christoph Niederbudde, BA Abschlussvortrag
Taylor series (the useful stuff from your calculus class)
- Datum: Wed, 19 Mar 2025, 14:00
- Ort: SR 301
- Vortragende(r): Jean-Pierre von der Heydt
- Inhalt: Recycled talk from the Klausurtagung
Forbidden Patterns in Mixed Linear Layouts
- Datum: Wed, 19 Feb 2025, 14:00
- Ort: SR 301
- Vortragende(r): Deborah Haun
Enumeration Algorithms for Dependencies in Databases
- Datum: Wed, 12 Feb 2025, 14:00
- Ort: SR 301
- Vortragende(r): Thomas Bläsius
Folding Trees
- Datum: Fri, 7 Feb 2025, 14:00
- Ort: SR 301
- Vortragende(r): Sven Geißler, PdF Short Presentation
- Inhalt: In the algorithm for fold and cut you need to also fold a tree flat in an optimal way if you want to obtain a simple crease pattern. In this talk we present this tree folding problem and some results about its complexity.
Engineering Matrix Product Correction Algorithms (B.Sc. thesis short presentation)
- Datum: Fri, 31 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Maximilian Limmer
Induced Covering Numbers
- Datum: Fri, 24 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Yidi Zang
- Inhalt: (Short Presentation)
Rerouting Curves on Surfaces
- Datum: Wed, 22 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Torsten Ueckerdt
Interactive Theorem Proving
- Datum: Wed, 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: Fri, 10 Jan 2025, 14:15
- Ort: SR 301
- Vortragende(r): Samuel Born, Masterarbeit Kurzvortrag
Lineplanning
- Datum: Fri, 10 Jan 2025, 14:00
- Ort: SR 301
- Vortragende(r): Maximilian Walz, Masterarbeit Kurzvortrag
Crossing Number of 2-Planar Graphs
- Datum: Wed, 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: Wed, 18 Dec 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: Wed, 18 Dec 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: Fri, 13 Dec 2024, 14:45
- Ort: SR 301
- Vortragende(r): Timo Fritsch, (MA Kurzvortrag)
Heuristics for FLaMECaST
- Datum: Fri, 13 Dec 2024, 14:30
- Ort: SR 301
- Vortragende(r): Simon Kienle, BA Kurzvortrag
Power Domination with Bounded Propagation
- Datum: Fri, 13 Dec 2024, 14:15
- Ort: SR 301
- Vortragende(r): Christoph Niederbudde, BA Kurzvortrag
CCH with edge insertion
- Datum: Fri, 13 Dec 2024, 14:00
- Ort: SR 301
- Vortragende(r): Benedikt Müller, Kurzvortrag Bachelorarbeit
Erd�-Posa property of cycles that are far apart
- Datum: Wed, 11 Dec 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: Fri, 6 Dec 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: Wed, 4 Dec 2024, 14:00
- Ort: SR 301
- Vortragende(r): Marvin Künnemann
Broadcast, Reduction and beyond with Block Schedules and Circulant Graphs
- Datum: Tue, 3 Dec 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: Wed, 27 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Wendy Yi
Degree Independent Weights for Weighted Graph Embeddings
- Datum: Fri, 22 Nov 2024, 14:45
- Ort: SR 301
- Vortragende(r): Karl Bernhard, BA Kurzvortrag
Algorithms for k-Power Dominating Set
- Datum: Fri, 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: Fri, 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: Wed, 20 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Mirza Redzic
Combining Vertex Orderings
- Datum: Fri, 15 Nov 2024, 14:45
- Ort: SR 301
- Vortragende(r): Moritz Bär, Kurzvortrag Msc - Ueckerdt
Algorithmic Aspects of Product Structure
- Datum: Fri, 15 Nov 2024, 14:30
- Ort: SR 301
- Vortragende(r): Antonia Heiming, Kurzvortrag Bachelorarbeit
Complexity of Solo Chess Variants
- Datum: Fri, 15 Nov 2024, 14:00
- Ort: SR 301
- Vortragende(r): Kolja Kühn, MA
Structure and Independence in Hyperbolic Uniform Disk Graphs
- Datum: Wed, 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: Fri, 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: Tue, 29 Oct 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: Fri, 25 Oct 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: Fri, 18 Oct 2024, 14:30
- Ort: SR 301
- Vortragende(r): Kilian Krause, Msc-Abschluss (Ueckerdt)
Generating Geometric Random Graphs with Boolean Distance Functions
- Datum: Fri, 18 Oct 2024, 14:00
- Ort: 101 (Sitzungszimmer)
- Vortragende(r): Maxime Rambaud, BA Vortrag
Frontiers of Randomised Data Structures
- Datum: Tue, 15 Oct 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: Thu, 10 Oct 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: Fri, 4 Oct 2024, 14:00
- Ort: SR 301
- Vortragende(r): Christoph Hoffmeyer, Msc-Thesis (Ueckerdt)
Sommersemester 2024
PdF Abschlussvortrag
- Datum: Fri, 27 Sep 2024, 15:00
- Ort: SR 301
- Vortragende(r): Deborah Haun
Bounding the Face Length of Girth-Planar Maximal Graphs
- Datum: Fri, 27 Sep 2024, 14:30
- Ort: SR 301
- Vortragende(r): Leon Kießle, Bsc-Thesis (Ueckerdt)
Freeze Tag Cop Number of Graphs
- Datum: Fri, 27 Sep 2024, 14:00
- Ort: SR 301
- Vortragende(r): Jonas Dalchow
Enumerating Alternative Paths
- Datum: Tue, 24 Sep 2024, 13:45
- Ort: SR 301
- Vortragende(r): Tim Domnick, Bachelorarbeit
Hyperbolic Sphericity
- Datum: Fri, 20 Sep 2024, 14:00
- Ort: SR 301
- Vortragende(r): Lennart Großkrkeutz
Intersection Graphs with and without Product Structure
- Datum: Fri, 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: Tue, 3 Sep 2024, 13:00
- Ort: SR 301
- Vortragende(r): Samuel Schneider
TBA
- Datum: Tue, 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: Fri, 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: Fri, 23 Aug 2024, 14:00
- Ort: SR 301
- Vortragende(r): Benedikt Hahn, Msc-Arbeit Ueckerdt
Exploring the Approximability Landscape of 3SUM
- Datum: Fri, 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: Tue, 13 Aug 2024, 13:00
- Ort: SR 301
- Vortragende(r): PdF student(s)
Epistemic EFX Allocations Exist for Monotone Valuations
- Datum: Tue, 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: Tue, 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: Fri, 28 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Tobias Hoch, BA Kurzvortrag
On Wegner`s Conjecture for Rectangle Intersection Graphs
- Datum: Fri, 21 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Anouk Sommer, Bsc-Defense Ueckerdt
Edge Densities and the Density Formula
- Datum: Fri, 14 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Benedikt Hahn, Msc-Ueckerdt Kurzvortrag
Einsichten zur L�sbarkeit von Solarparkverkabelungs-Problemen
- Datum: Tue, 11 Jun 2024, 13:00
- Ort: SR 301
- Vortragende(r): Thomas Oltmann, MA Abschlussvortrag
PdF Vortr�ge
- Datum: Fri, 7 Jun 2024, 14:15
- Ort: SR 301
- Vortragende(r): Sven, Elly und Henrik, Deborah
Freeze Tag Cop Number of Graphs
- Datum: Fri, 7 Jun 2024, 14:00
- Ort: SR 301
- Vortragende(r): Jonas Dalchow
Solo Chess
- Datum: Fri, 24 May 2024, 14:30
- Ort: SR 301
- Vortragende(r): Kolja Kühn, Kurzvortrag
Kurzvortrag: Stack Number of Upwards Planar k-Trees
- Datum: Fri, 24 May 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: Fri, 24 May 2024, 14:00
- Ort: SR 301
- Vortragende(r): Tim Domnick, Kurzvortrag
Hyperbolic Sphericity
- Datum: Fri, 17 May 2024, 14:00
- Ort: SR 301
- Vortragende(r): Lennart Großkrkeutz, BA Kurzvortrag
How to Reduce Temporal Cliques to Find Sparse Spanners
- Datum: Fri, 10 May 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: Fri, 10 May 2024, 14:00
- Ort: SR 301
- Vortragende(r): Annemarie Schaub, Kurzvortrag Bachelorarbeit (scale)
Multi Via-Node Alternatives for Customized Contraction Hierarchies
- Datum: Fri, 3 May 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: Fri, 19 Apr 2024, 14:30
- Ort: SR 301
- Vortragende(r): Oguz Mutlu
Theoretical Study of Data Reduction in Real-World Hitting Set Instances
- Datum: Fri, 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: Fri, 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.