Research Colloquium (Winter Term 2020/2021)

We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and, in addition to a global budget limit, we are given several groupings of projects, each group with its own budget limit. We mention several natural use-cases of this generalization and study the computational complexity of identifying project bundles that maximize voter satisfaction while respecting all budget limits. While we show that the problem is generally intractable, we describe efficient exact algorithms for several special cases, including instances with only few groups and instances where the structure of the groups is close to be laminar, as well as efficient approximation algorithms. Our positive algorithmic results allow, e.g., municipalities to hold richer PB processes that are thematically and geographically inclusive.

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k ≤ m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.

Based on joint work with Klaus Heeger, Danny Hermelin, George B. Mertzios, Rolf Niedermeier, and Dvir Shabtay

Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called c-closure, for a parameterized study of clique enumeration problems. A graph G is c- closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of G is the smallest c such that G is c-closed. We systematically explore the impact of c-closure on the computational complexity of detecting and enumerating small induced subgraphs. More precisely, for each graph H on three or four vertices, we investigate parameterized polynomial-time algorithms for detecting H and for enumerating all occurrences of H in a given c-closed graph.

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

In the Hospital Residents problem with lower and upper quotas (HR−QUL), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero [Biró et al., TCS 2010]. We analyze this problem from a parameterized perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, we present a polynomial-time algorithm that finds a stable matching if it exists on instances with maximum lower quota two. Alongside HR−QUL, we also consider two closely related models of independent interest, namely, the special case of HR−QUL where each hospital has only a lower quota but no upper quota and the variation of HR−QULwhere hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas.

Based on joint work with Klaus Heeger

We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer). In contrast to other versions of TSP accounting for physical constraints, such as Dubins TSP, the spirit of this model is that (1) no speed limitations apply, and (2) inertia depends on the current velocity. As such, this model is closer to typical models considered in path planning problems, although applied here to the visit of n cities in a non-predetermined order. We motivate and introduce the VectorTSP problem, discussing fundamental differences with previous versions of TSP. In particular, an optimal visit order for ETSP may not be optimal for VTSP. We show that VectorTSP is NP-hard, and in the other direction, that VectorTSP reduces to GroupTSP in polynomial time (although with a significant blow-up in size). On the algorithmic side, we formulate the search for a solution as an interactive scheme between a high-level algorithm and a trajectory oracle, the former being responsible for computing the visit order and the latter for computing the cost (or the trajectory) for a given visit order. We present algorithms for both, and we demonstrate and quantify through experiments that this approach frequently finds a better solution than the optimal trajectory realizing an optimal ETSP tour, which legitimates the problem itself and (we hope) motivates further algorithmic developments.

A graph whose edges only appear at certain points in time is called a temporal graph. In a temporal graph, two vertices are said to be connected if there is a temporal path between them, that is a path which traverses edges in chronological order. We consider a simple model of a random temporal graph, obtained by assigning to every edge of an Erdős–Rényi random graph G_n,p a uniformly random presence time in the real interval [0, 1]. We study several connectivity properties of this random temporal graph model and uncover a surprisingly regular sequence of sharp thresholds for these properties. Finally, we discuss how our results can be transferred to other random temporal graph models.

Bayesian Network Structure Learning (BNSL) is motivated by finding conditional dependencies of random variables such that these dependencies describe multivariate probability distribution as closely as possible. In the computational problem one is given a set of vertices N and a family of so-called local scores and one aims to find an arc-set A such that (N,A) is a directed acyclic graph and the score is maximized. In this talk, I will present results on the parameterized complexity of BNSL when additional structureal constraints are posed on the network or on its so-called moralized graph. For example, I present an XP algorithm for BNSL under the constraint that the moralized graph has a small dissociation number when parameterized by the size of the dissociation set. This result is complemented by hardness results.

An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.

A temporal graph is a sequence of graphs (called layers) over the same vertex set --- describing a graph topology which is subject to discrete changes over time. A Δ-temporal matching M is a set of time edges (e,t) (an edge e paired up with a point in time t) such that for all distinct time edges (e,t),(e′,t′)∈M we have that e and e′ do not share an endpoint, or the time-labels t and t′ are at least Δ time units apart. Mertzios et al. [STACS '20] provided a 2^O(Δν)⋅|G|^O(1)-time algorithm to compute the maximum size of Δ-temporal matching in a temporal graph G, where |G| denotes the size of G, and ν is the Δ-vertex cover number of G. The Δ-vertex cover number is the minimum number of vertices which are needed to hit (or cover) all edges in any Δ consecutive layers of the temporal graph. We show an improved algorithm to compute a Δ-temporal matching of maximum size with a running time of Δ^O(ν)⋅|G| and hence provide an exponential speedup in terms of Δ.

We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i.e., a triangle). The best known algorithms for triangle finding in an n- node graph take O(nω) time, where ω < 2.373 is the ma- trix multiplication exponent. We give a general randomized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes, in O(n^ω) time with high probability. The algorithm can be derandomized in some cases: we show how to detect a diamond (or its complement) in deterministic O(n^ω) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C4 detection ran in O(n3.3) time, and for diamond detection in O(n3) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O(m^2ω /(ω +1) ) ≤ O(m1.41) time. We give a randomized O (m^2ω /(ω +1)) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C4, K4 and their complements. In the case of diamond detection, we also design a deterministic O(m^2ω /(ω +1) ) time algorithm. For C4 or its complement, we give randomized O(m^(4ω −1)/(2ω +1) ) ≤ O(m^1.48 ) time finding algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in O(m1.5) time.

Abstract: Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n ≥ 3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms for determining Hamiltonicity when either of the two conditions are relaxed. More precisely, we show that the Hamiltonian Cycle problem can be solved in time ck · nO(1), for a fixed constant c, if at least n − k vertices have degree at least n/2, or if all vertices have degree at least n/2 − k. The running time is, in both cases, asymptotically optimal, under the exponential-time hypoth- esis (ETH). The results extend the range of tractability of the Hamiltonian Cycle problem, showing that it is fixed-parameter tractable when parameterized below a natural bound. In addition, for the first param- eterization we show that a kernel with O(k) vertices can be found in polynomial time.

Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W_1 from W_2, that is, in every region into which the lines partition the plane there are either only points of W_1, or only points of W_2, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: we would like to discretize the range of x-coordinates and the range of y-coordinates into as few segments as possible, maintaining that no pair of points from W_1 times W_2 are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time 2^O(k^2 log k) n^O(1), where k is the bound on the number of lines to find and n is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel. This is a joint work with Stefan Kratsch, Tomáš Masařík, Irene Muzi, and Marcin Pilipczuk.

We study q-SAT in the multistage model, focusing on the linear-time solvable 2-SAT. Herein, given a sequence of q-CNF fomulas and a non-negative integer d, the question is whether there is a sequence of satisfying truth assignments such that for every two consecutive truth assignments, the number of variables whose values changed is at most d. We prove that Multistage 2-SAT is NP-hard even in quite restricted cases. Moreover, we present parameterized algorithms (including kernelization) for Multistage 2-SAT and prove them to be asymptotically optimal.

Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different "gender" (this is Stable Marriage) or "unrestricted" (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases.

Here, we focus on the study of Multidimensional Stable Roommates, known to be NP-hard since the early 1990's. Many NP-hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on "objective" scores, one roughly speaking assumes that all agent preferences are "derived from" a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) stable matching case, but seemingly almost never for the multidimensional case.

This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists.

In parliamentary elections, parties compete for a limited, typically fixed number of seats. They face the question of how to spend their campaign resources: to convince voters that do not plan to vote (abstainers) or to persuade voters that otherwise would have voted for other parties. We study this question for popular apportionment methods from a computational point of view. In particular, we study the corresponding so-called bribery problem, i.e., what is the most effective strategy to gain more seats by convincing a given number of voters to vote for a given party. We also run extensive experiments on real-world election data and measure the effectiveness of targeted campaign management.

Given a matrix A∈R^n×n, we consider the problem of maximizing x^TAx subject to the constraint x∈−1,1^n. This problem, called MaxQP by Charikar and Wirth [FOCS'04], generalizes MaxCut and has natural applications in data clustering and in the study of disordered magnetic phases of matter. Charikar and Wirth showed that the problem admits an Ω(1/lgn) approximation via semidefinite programming, and Alon, Makarychev, Makarychev, and Naor [STOC'05] showed that the same approach yields an Ω(1) approximation when A corresponds to a graph of bounded chromatic number. Both these results rely on solving the semidefinite relaxation of MaxQP, whose currently best running time is O(n^1.5⋅minN,n^1.5), where N is the number of nonzero entries in A, ignoring polylogarithmic factors.

In this sequel, we abandon the semidefinite approach and design purely combinatorial approximation algorithms for special cases of MaxQP where A is sparse (i.e., has O(n) nonzero entries). Our algorithms are superior to the semidefinite approach in terms of running time, yet are still competitive in terms of their approximation guarantees. More specifically, we show that: - MaxQP admits a (1/2Δ)-approximation in O(n lg n) time, where Δ is the maximum degree of the corresponding graph. - UnitMaxQP, where A∈−1,0,1^n×n, admits a (1/2d)-approximation in O(n) time when the corresponding graph is d-degenerate, and a (1/3δ)-approximation in O(n^1.5) time when the corresponding graph has δn edges. - MaxQP admits a (1−ε)-approximation in O(n) time when the corresponding graph and each of its minors have bounded local treewidth. - UnitMaxQP admits a (1−ε)-approximation in O(n^2) time when the corresponding graph is H-minor free.

This is joint work with Danny Hermelin, Rolf Niedermeier, and Rami Pugatch.