Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. ucz.

Information

Home page

Research fields

• Algorithmics

List of talks

• Feb. 20, 2026, 2:15 p.m.
  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 …

  ---

• Jan. 16, 2026, 2:15 p.m.
  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 …

  ---

• Dec. 5, 2025, 2:15 p.m.
  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 …

  ---

• Nov. 28, 2025, 2:15 p.m.
  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 …

  ---

• Oct. 17, 2025, 2:15 p.m.
  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 …

  ---

• June 6, 2025, 2:15 p.m.
  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 …

  ---

• May 16, 2025, 2:15 p.m.
  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 …

  ---

• April 25, 2025, 2:15 p.m.
  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 …

  ---

• April 4, 2025, 2:15 p.m.
  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 …

  ---

• March 21, 2025, 2:15 p.m.
  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). …

  ---

• March 14, 2025, 2:15 p.m.
  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 …

  ---

• Feb. 28, 2025, 2:15 p.m.
  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 …

  ---

• Jan. 17, 2025, 2:15 p.m.
  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 …

  ---

• Dec. 6, 2024, 2 p.m.
  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 …

  ---

• Nov. 29, 2024, 2:15 p.m.
  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 …

  ---