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