Noon seminar

The informal research seminar of the ALGA group. Talks last roughly 25 minutes, with five extra minutes allocated for discussion. Many presentations are focused on recent conference presentations, or practice talks for upcoming conferences. New members are often asked to give an overview of their field of research. Talks given by invited speakers may take up to 45–60 minutes including questions.

To be kept up-to-date about noon seminar presentations, please subscribe to the algoseminar-l mailing list.

This is the schedule for 2022. Schedules are available between 2005 and 2022.

• Presentation
• Master's defense
• Midterm
• Invited talk
• External talk
• Practice talk
• PhD defense
• Cancelled

Upcoming talks

Send an email to Alex to schedule your talk.

• Jul 08, 11:00—11:40 (TBA)
  Geert van Wordragen: New Results for Discrete Voronoi Games.
  － Abstract
  

  TBA

Past talks

• Jun 27, 11:30—12:00 (MF 13)
  Sampson Wong: Improving the Dilation of a Metric Graph by Adding Edges.
  － Abstract
  

  Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of $k$ edges, which $k$ edges do we add to produce a minimum-dilation graph? The special case where $k = 1$ has been studied in the past, but no major breakthroughs have been made for $k > 1$. We provide the first positive result, an $O(k)$-approximation algorithm that runs in $O(n^3 \log n)$ time.

• Jun 27, 11:00—11:30 (MF 13)
  Jad Bassil: Self-Reconfiguration for Modular Robotic Programmable Matter Using a Porous Structure.
  － Abstract
  

  I will present 3D Catoms and how they can be arranged in a porous structure to improve self-reconfiguration by allowing parallel flow of modules inside of the structure without collisions or blocking. Then, present a self-reconfiguration algorithm based on max-flow search to transform the structure into a given goal shape.

• Jun 24, 13:00—13:40 (MF 15)
  Kees Voorintholt: Efficient and Robust Distributed Algorithms for Minimum Spanning Tree.
  － Abstract
  

  Clustering of data plays a central role in Computer Science. Particular applications are recommendation engines, search engines, and image segmentation to name a few. Minimum Spanning Tree (MST)-based algorithms are among the most popular clustering algorithms. This includes agglomerative clustering, Cure, and affinity clustering. However, the amount of data to analyze is increasing at a very fast rate every day. Hence there is a need for new solutions to efficiently compute effective different variations of the classical hierarchical clustering on BigData. The current distributed clustering algorithms, based on building a Minimum Spanning Tree have two weaknesses:
  • MST-based clustering algorithms are not space and work efficient.
  • They are not robust against sudden changes in the network and even a small change can completely change the shape of these clusterings.
  
  In this thesis, we address these issues. In particular, we have the following results:
  • We obtain the first space and work efficient distributed algorithm for the MST problem in dense networks (in the MapReduce model).
  • We benchmark the performance of our distributed algorithm against well-known distributed algorithms using synthetic datasets and real-world social networks and observe that the communication complexity of our algorithm is the smallest among these algorithms.
  • We propose an optimization of the affinity clustering algorithm (i.e., distributed implementation of Borůvka's algorithm for MST problem) where we randomly perturb edge weights and classify the perturbed edges in a logarithmic number of buckets and we empirically show that this improved affinity clustering is more robust against small changes in networks.

• Jun 20, 13:00—14:00 (MF 15)
  Tom Peters: On the Computational Power of Energy-Constraint Mobile Robots: Algorithms and Cross-Model Analysis.
  － Abstract
  

  The talk is 25 minutes, the rest is scheduled for questions and feedback.
  
  We consider distributed systems of identical autonomous computational entities, called robots, moving and operating in the plane in synchronous Look–Compute–Move (LCM) cycles. The algorithmic capabilities of these systems have been extensively investigated in the literature under four distinct models (Oblot, FSta, FCom, Lumi), each identifying different levels of memory persistence and communication capabilities of the robots. Despite their differences, they all always assume that robots have unlimited amounts of energy.
  
  In this paper, we remove this assumption and start the study of the computational capabilities of robots whose energy is limited, albeit renewable. We first study the impact that memory persistence and communication capabilities have on the computational power of such energy-constrained systems of robots; we do so by analyzing the computational relationship between the four models under this energy constraint. We provide a complete characterization of this relationship.
  
  We then study the difference in computational power caused by the energy restriction and provide a complete characterization of the relationship between energy-constrained and unrestricted robots in each model. We prove that within Lumi there is no difference; an integral part of the proof is the design and analysis of an algorithm that in Lumi allows energy-constrained robots to execute correctly any protocol for robots with unlimited energy. We then show the (apparently counterintuitive) result that in all other models, the energy constraint actually provides the robots with a computational advantage.

• May 31, 13:00—13:40 (MF 3)
  Pieter Voors: The Dynamic Relay Placement Problem: Completing Mesh Networks of Moving Sensors.
  － Abstract
  

  In the relay placement problem, given a set of static sensors and relay range r ≥ 1, we must place a minimum number of static relays such that any two sensors can communicate via the multi-hop wireless sensor network with communication ranges 1 and r for sensors and relays respectively. Allowing sensors to communicate directly or not (1- versus 2-tiered) and providing options for relay placement or not (discrete versus continuous) gives multiple variations. We extend this to the dynamic relay placement problem where sensors move along given paths, requiring full connectivity at any point in time, and explore the implications of this for all combinations of these variations in the 2D Euclidean plane.
  
  All variations are proven to be NP-complete. We show that it is NP-hard to approximate the 1-tiered variants within a constant factor and propose an exponential-time 4-approximation algorithm. We construct approximation schemas for the 2-tiered continuous variant that combine an existing problem with the newly proposed NP-complete line segment unit disc cover problem, for which we create various O(1)-approximation algorithms. For the 2-tiered discrete variant, we create an approximation schema using the existing static variant of it and optimize existing algorithms for it in the process.

• May 31, 11:30—12:15 (MF 6.131)
  Jules Wulms: The Influence of Dimensions on the Complexity of Computing Decision Trees.
  － Abstract
  

  A decision tree recursively splits a feature space $\mathbb{R}^d$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number $d$ of dimensions of the feature space. We show that it can be solved in $O(n^{2d + 1})$ time, but under reasonable complexity-theoretic assumptions it is not possible to achieve $f(d) \cdot n^{o(d / \log d)}$ running time, where $n$ is the number of training examples. The problem is solvable in $(dR)^{O(dR)} \cdot n^{1+o(1)}$ time, if there are exactly two classes and $R$ is an upper bound on the number of tree leaves labeled with the first class.

• May 30, 10:45—11:25 (MF 14)
  Youri Sio: Hypergraph Crossing Minimization.
  － Abstract
  

  The crossing number is considered a standard quality criterion in (hyper)graph drawings. However, determining the crossing number is NP-hard. Current hypergraph drawing algorithms do not always exploit the subtle differences between the various hypergraph drawing methods. We find that the edge-based drawing method can have a strictly lower crossing number than the incidence representation by reinserting hyperedges as minimum crossing Steiner trees. In addition, we found that hypergraph supports can be optimized for minimum crossings with limited to no effect on the support length. The introduced algorithms are implemented on top of existing software libraries and then evaluated on their performance. Using these algorithms, hypergraph supports can often be drawn with significantly fewer crossings at the cost of a small increase in support length, and edge-based hypergraph drawings can have a lower crossing number than what is possible in the incidence representation.

• May 24, 11:30—12:15 (MF 15)
  Soeren Nickel: Unit Disk Representations of Embedded Trees, Outerplanar and Multi-Legged Graphs.
  － Abstract
  

  A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that, using dynamic programming, it can be decided in linear time if a lobster graph admits a monotone weak UDC, which permits intersections between disks of non-adjacent vertices.

• Mar 21, 13:30—14:10 (MF 2)
  Thomas Derwig: A Kinetic Clustering Using DBSCAN.
  － Abstract
  

  This paper looks into clustering a data set consisting of moving points. Specifically it proposes multiple algorithms to create and more importantly efficiently update a DBSCAN clustering for moving points. That is, to efficiently update the clustering without completely recomputing it when only part of the data changes. For this type of clustering there is no previous research done into maintaining it for moving points, thus this paper gives an initial proposal that sees some success but is also meant to be further built upon. This initial approach is focused on adapting existing algorithms by identifying components that are not necessary to update the clustering for a single point change and pruning these to get a streamlined version that can perform localized cluster update only where an update is needed. Furthermore it explores ways to create an approximate clustering based on various different properties of the updates to the data. These proposed algorithms were tested on a limited but relevant data set. The algorithms proposed in this paper can be used to more efficiently compute consecutive clusterings for any locational data that changes with time such as an analysis of movement trajectories using clustering at different points in time.

• Mar 17, 15:00—15:40 (Zwarte Doos 1.03)
  Jeroen Schols: Kernelization for Treewidth-2 Vertex Deletion.
  － Abstract
  

  The Treewidth-2 Vertex Deletion problem asks whether a set of at most $t$ vertices can be removed from a graph, such that the resulting graph has treewidth at most two. A graph has treewidth at most two if and only if it does not contain a $K_4$ minor. Hence, this problem corresponds to the NP-hard $F$-Minor Cover problem with $F = \{K_4\}$. For any variant of the $F$-Minor Cover problem where $F$ contains a planar graph, it is known that a polynomial kernel exists, i.e., a preprocessing routine that in polynomial time outputs an equivalent instance of size $t^{O(1)}$. However, this proof is non-constructive, meaning that this proof does not yield an explicit bound on the kernel size. The $\{K_4\}$-Minor Cover problem is the simplest variant of the $F$-Minor Cover problem with an unknown kernel size.
  
  To develop a constructive kernelization algorithm, we present a new method to decompose graphs into near-protrusions, such that near-protrusions in this new decomposition can be reduced using elementary reduction rules. Our method extends the ‘approximation and tidying’ framework by van Bevern et al. [Algorithmica 2012] to provide guarantees stronger than those provided by both this framework and a regular protrusion decomposition. Furthermore, we provide extensions of the elementary reduction rules used by the $\{K_4, K_{2,3}\}$-Minor Cover kernelization algorithm introduced by Donkers et al. [IPEC 2021].
  
  Using the new decomposition method and reduction rules, we obtain a kernel consisting of $O(t^{41})$ vertices, which is the first constructive kernel. This kernel is a step towards more concrete kernelization bounds for the $F$-Minor Cover problem where $F$ contains a planar graph, and our decomposition provides a potential direction to achieve these new bounds.

• Mar 08, 10:30—12:00 (Hybrid: MF 3.122, Zoom)
  Aleksandr Popov, Tom Peters, and Max van Mulken: EuroCG Practice Talks.
  － Abstract
  

  The talks are 12 minutes long in 15-minute slots. We schedule 30 minutes per talk to accommodate questions and feedback.
  1. Aleksandr Popov — Segment Visibility Counting Queries in Polygons
  2. Tom Peters — Fast Reconfiguration for Programmable Matter
  3. Max van Mulken — Kinetic Group Density in 1D

• Jan 31, 11:00—12:00 (MF 3)
  David Dekker: Kernelization for Feedback Vertex Set via Elimination Distance to a Forest.
  － Abstract
  

  We study efficient preprocessing of the Feedback Vertex Set problem, a fundamental problem in graph theory which asks for a minimum vertex set whose removal yields an acyclic graph. More precisely, we aim to determine for which parameterizations this problem admits a polynomial kernel. While a characterization is known for the related Vertex Cover problem, it remained an open problem whether this could be generalized to Feedback Vertex Set. We prove that this problem has a polynomial kernel when parameterized by the deletion distance to a graph of bounded elimination distance to a forest. Furthermore, we prove that no polynomial kernel exists when one uses the deletion distance to a minor-closed graph class that has unbounded elimination distance to a forest as parameterization. We thereby give a characterization of which parameterizations allow a polynomial kernel for this problem, which surprisingly differs from the known characterization of Vertex Cover.