Seminar Algorithms

Organizers

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

Information

Home page

List of talks

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

  ---

• Nov. 8, 2024, 2:15 p.m.
  Anita Dürr (Max Planck Institute for Informatics)
  Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
  We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time ˜O(n + t√pmax), where n is the number of items, t is the knapsack capacity, and pmax is the maximum item profit. …

  ---

• Oct. 25, 2024, 2:15 p.m.
  Maël Dumas
  On graphs coverable by k shortest paths
  We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single exponential function of k. As …

  ---

• Oct. 18, 2024, 2:15 p.m.
  Konrad Majewski
  Parameterized Dynamic Data Structure for Split Completion
  We design a randomized data structure that, for a fully dynamic graph G updated by edge insertions and deletions and integers k, d fixed upon initialization, maintains the answer to the Split Completion problem: whether …

  ---