Organizatorzy

dr hab. Michał Pilipczuk, prof. ucz.

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://students.mimuw.edu.pl/~kd417818/algorithms-seminar/

Dziedziny badań

Algorytmika

Lista referatów

20 lutego 2026 14:15
Kacper Kluk
Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveling Salesperson Problem. Our lower bounds are higher than the …
16 stycznia 2026 14:15
Jan Kwieciński
BMSSP - Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
The single-source shortest path (SSSP) problem is a fundamental problem in graph algorithms. In 1959 E. W. Dijkstra proposed a O(m + n log n) algorithm. Since then, many algorithms have exploited various properties of …
5 grudnia 2025 14:15
Julien Duron
Sharp bounds on the size of long induced paths in graphs
Given a graph containing a path on n vertices, what guarantees can we have on the maximal size of an induced path? In 1982 Galvin, Rival and Sands proved that there is an unbounded function …
28 listopada 2025 14:15
Daniel Mock (RWTH Aachen University)
Testing H-freeness on sparse graphs, the case of bounded expansion
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P , it decides with high probability whether the graph …
17 października 2025 14:15
Anita Dürr (Saarland University and Max Planck Institute for Informatics)
Faster algorithms for k-Orthogonal Vectors in low dimension
In the Orthogonal Vectors problem (OV), we are given two families A, B of subsets of {1, ..., d}, each of size n, and the task is to decide whether there exists a pair a …
6 czerwca 2025 14:15
Jeremi Gładkowski
First-order transducibility among classes of sparse graphs
Transducibility is a notion from model theory that formalizes the idea of performing a logical operation on a graph. A class of graphs D is transducible from a class C if every graph from D …
16 maja 2025 14:15
Colin Geniet
χ-boundedness of bounded merge-width graphs
Merge-width is a generalisation of twin-width and bounded expansion classes, recently introduced by Dreier and Toruńczyk, for which the first-order model checking problem is FPT. This talk presents some elementary proofs of combinatorial properties of …
25 kwietnia 2025 14:15
Jadwiga Czyżewska
On coarse tree decompositions and coarse balanced separators
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer k such that for every weighing of the vertices, the graph admits …
4 kwietnia 2025 14:15
Florian Hörsch (CISPA)
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and a demand graph H on a set T ⊆ V (G) of terminals, the task is …
21 marca 2025 14:15
Marta Piecyk
Graph homomorphism problem parameterized by cutwidth
For a fixed (target) graph H, in the graph homomorphism problem, denoted by Hom(H), we are given a graph G, and we have to determine whether there exists an edge preserving mapping f: V(G)-> V(H). …
14 marca 2025 14:15
Michał Pilipczuk
Erdős-Pósa property of tripods in directed graphs
A tripod in a directed graph D with sources S and sinks T is a subgraph consisting of the union of two S-T-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart …
28 lutego 2025 14:15
Marek Sokołowski (Max Planck Institute for Informatics)
Fully dynamic biconnectivity in Õ(log² n) time
We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph, i.e., the vertices whose removal would disconnect the graph. Our data structure supports insertion and deletion of edges, as …
17 stycznia 2025 14:15
Rose McCarty
Separators in sphere intersection graphs
We discuss the sphere dimension of graphs. This is the smallest integer d such that the graph can be represented as the intersection graph of a collection of spheres in R^d. We show that graphs …
6 grudnia 2024 14:00
Szymon Toruńczyk
Merge-width and First-Order Model Checking
We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized coloring numbers. Graph classes of bounded merge-width – for which the radius-r merge-width parameter …
29 listopada 2024 14:15
Marcin Pilipczuk
Bounding ε-scatter dimension via metric sparsity
A recent work of Abbasi et al. [FOCS 2023] introduced the notion of ε-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range …