Seminar Algorithms

Organizers

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

Information

Home page

Research fields

• Algorithmics

List of talks

• 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 …

  ---

• Nov. 22, 2024, 2:15 p.m.
  Kunal Dutta
  A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels
  Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, compared to other typical …

  ---

• Nov. 15, 2024, 2:15 p.m.
  Wiktor Zuba
  Space-Efficient Indexes for Uncertain Strings
  Strings in the real world are often encoded with some level of uncertainty, for example, due to: unreliable data measurements; flexible sequence modeling; or noise introduced for privacy protection. In the character-level uncertainty model, an …

  ---