Antonio Lauerbach

Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper et al.

A mixed graph contains (undirected) edges as well as (directed) arcs, thus generalizing undirected and directed graphs. A proper coloring c of a mixed graph G assigns a positive integer to each vertex such that c(u)!=c(v) for every edge {u,v} and c(u)<c(v) for every arc (u,v) of G. As in classical coloring, the objective is to minimize the number of colors. Thus, mixed (graph) coloring generalizes classical coloring of undirected graphs and allows for more general applications, such as scheduling with precedence constraints, modeling metabolic pathways, and process management in operating systems; see a survey by Sotskov [Mathematics, 2020]. We initiate the systematic study of the parameterized complexity of mixed coloring. We focus on structural graph parameters that lie between cliquewidth and vertex cover, primarily with respect to the underlying undirected graph. Unlike classical coloring, which is fixed-parameter tractable (FPT) parameterized by treewidth or neighborhood diversity, we show that mixed coloring is W[1]-hard for treewidth and even paraNP-hard for neighborhood diversity. To utilize the directedness of arcs, we introduce and analyze natural generalizations of neighborhood diversity and cliquewidth to mixed graphs, and show that mixed coloring becomes FPT when parameterized by mixed neighborhood diversity. Further, we investigate how these parameters are affected if we add transitive arcs, which do not affect colorings. Finally, we provide tight bounds on the chromatic number of mixed graphs, generalizing known bounds on mixed interval graphs.

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Antonio Lauerbach et al.

Motivated by the controller placement problems in software-defined networks and the fair division principles of classical "cake cutting", we investigate the following two-player zero-sum game. In our model, a defender places a limited number of controllers on graph vertices, while an attacker deletes a limited number of vertices. The defender score is the total number of surviving vertices reachable from any remaining controller. We formalize the computational problems associated with various game dynamics (defender plays first; attacker plays first; players play simultaneously; pure or mixed strategies). We show that these natural problems are $\mathsf{NP}$-complete or $Σ^\mathsf{P}_2$-complete, depending on the specific variant. These hardness results provide limitations for optimal controller placement algorithms under different notions of quality of a solution. Finally, we present structural insights that yield efficient algorithms for restricted graph classes (namely interval graphs and graphs of bounded treewidth).

Antonio Lauerbach, Kendra Reiter, Marie Schmidt

Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride problem (LiDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the LiDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the LiDARP, and the problem to determine the minimum number of turns needed in an optimal LiDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the LiDARP and MinTurn problem.