We introduce the problem of Matroid-Constrained Vertex Cover: given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose a subset of vertices that is independent in the matroid, with the objective of maximizing the total weight of covered edges. This problem is a generalization of the much studied \textsc{max $k$-vertex cover} problem, in which the matroid is the simple uniform matroid.

This problem is APX-hard and also W[1]-hard (with k, the rank of the matroid, being the paramter). Nonetheless, in this work, by two different techniques, we are able to design Fixed-Parameter Tractable Approximation Schemes (FPT-AS) for this problem.

This is joint-work with François Sellier at École des Mines.

In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for non-preemptive version of the problem. We achieve this by revisiting the algorithm Lazy recently suggested in [WAOA, 2022] and giving an improved and tight analysis. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural Replan algorithm.

In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. In other words, a (partial) Grundy coloring of a graph G is a proper vertex coloring such that (at least one) any vertex v colored with color i has a neighbor of color j, for every j smaller than i. In this talk, I will discuss an FPT algorithm for Partial Grundy Coloring on general graphs.

Domination problems in general can capture situations in which some entities have an effect on other entities (and sometimes on themselves). The usual goals are either to select a minimum number of entities that can influence a target group of entities or to influence a maximum number of target entities with a certain number of available influencers. In this work we focus on the distinction between the standard and a novel notion of domination, which we call external domination; as we will discuss this distinction is meaningful in the context of the maximization objective. In particular, a dominator can dominate its entire neighborhood in a graph, including itself, while those of its neighbors which are not dominators themselves are externally dominated.We study the problem of maximizing the external domination that a given number of dominators can yield and we present an 0.5307-approximation algorithm for this problem, introducing new techniques that exploit the structure of suitably chosen subgraphs of the input graph. Moreover, our methods provide a framework for approximating a number of problems that can be cast in terms of external domination, including social network and facility location problems, as well as representation problems arising in the area of computational social choice. In particular, we observe that a generalization of external domination can capture a new problem in elections, in which we want to maximize the number of externally represented voters, that is, voters that are not elected, but a candidate of their choice is. We study this problem in two different settings and provide approximability analysis for both. Our results reveal, among other contributions, that an earlier resource allocation algorithm can be suitably adapted so as to yield a 0.462-approximation algorithm for maximum external domination in directed graphs.

We show that a wide selection of connectivity problems in undirected graphs is fixed-parameter tractable parameterized by the independence number of the graph (i.e., the size of the maximum independent set); in particular this holds for finding structures such as Hamiltonian paths, maximum path covers, largest linkages and topological minors. To the best of our knowledge, this is the first family of non-trivial FPT results for this parameterization.

As a second step, we use the above result to show an algorithmic extension of the theorem of Gallai and Milgram from 1960: The original theorem states that the vertex set of every graph G can be covered by α(G) vertex-disjoint paths, where α(G) is the independence number of G. We show that it can be determined whether the vertex set of G can be covered by α(G)-k vertex-disjoint paths in time f(k) ⋅ poly(n), for a certain function f(⋅).

TBA

In this unusual seminar talk (or rather, live coding session), I will start from scratch to build, run, and visualize experiments using Python and R. Our toy problem will be to analyze the run time of (1+1)-EAs with varying mutation probabilities. During the session, I will share some of my learnings from running and visualizing algorithm experiments, and I want you to share yours too.

In this work, we study a generalization of the seminal Hotelling-Downs model through the lens of parameterized complexity. In this model, there is a set of voters on a line and a set of parties that compete over them. Each party has to choose a nominee from a set of candidates with predetermined positions on the line, where each candidate could come at a different cost. The goal of every party is to choose the most profitable nominee, given the nominees chosen by the rest of the parties. We ask: what is the complexity of deciding whether a pure Nash equilibrium exists for this model, under several natural parameters? In this seminar, I will talk about the model and briefly explain one of our results if time allows!

TBA

In this talk, our three young and ambitious scientists will each present us briefly a paper they felt like showing us. Each talk will be 5 minutes long and invite for discussion.

Upward Planarity Testing and Orthogonal Planarity Testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth [Orthogonal: GD'19; Upward: SoCG'22].

In this talk, I will show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems.

We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known n^{O(tw)}-time algorithms cannot be improved to run in time n^{o(tw)} unless the Exponential Time Hypothesis fails.

Joint work with Bart M. P. Jansen, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov

Managing and organizing research materials is a non-trivial task for academics. Zotero, a free and open-source software, can help you collect, organize, cite and share your references. In this short introduction, Stefan will guide us through the different functionalities of Zotero and demonstrate how it can be used during the research process.

River is a single-winner, Condorcet-consistent voting method that is based on pairwise margins and can be seen as a simplified variation of Tideman's Ranked Pairs method. Like Ranked Pairs and Schulze's Beat Path, River is a refinement of the Split Cycle method and shares many desirable properties with these. Unlike the other three methods, River satisfies a strong form of resistance to agenda-manipulation that is known as independence of Pareto-dominated alternatives. We will look at axiomatic properties of River and analyse our experimental results to establish that River provides a compromise between Ranked Pairs and Beat Path.

TBA