Rolf Niedermeier

AIJ Journal 2025 Journal Article

Drawing a map of elections

• Stanisław Szufa
• Niclas Boehmer
• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i. e. , collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e. g. , the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space, we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.

TCS Journal 2024 Journal Article

Approximating sparse quadratic programs

• Danny Hermelin
• Leon Kellerhals
• Rolf Niedermeier
• Rami Pugatch

Given a matrix A ∈ R n × n, we consider the problem of maximizing x T A x 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 / lg ⁡ n ) 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 ⋅ min ⁡ { N, n 1. 5 } ), where N is the number of nonzero entries in A and O ˜ ignores 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 Δ = O ( 1 ) is the maximum degree of the corresponding graph. • Unit MaxQP, where A ∈ { − 1, 0, 1 } n × n, admits a ( 1 / 2 d ) -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 for δ = O ( 1 ). • MaxQP admits a ( 1 − ε ) -approximation in O ( n ) time when the corresponding graph and each of its minors have bounded local treewidth. • Unit MaxQP admits a ( 1 − ε ) -approximation in O ( n 2 ) time for H-minor free graphs.

JAAMAS Journal 2024 Journal Article

Equilibria in schelling games: computational hardness and robustness

• Luca Kreisel
• Niclas Boehmer
• Rolf Niedermeier

Abstract In the simplest game-theoretic formulation of Schelling’s model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI ’20] and Elkind et al. [IJCAI ’19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

AAAI Conference 2023 Conference Paper

Fair Short Paths in Vertex-Colored Graphs

• Matthias Bentert
• Leon Kellerhals
• Rolf Niedermeier

The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally valuable. For the setting where each vertex is assigned to a group (color), we provide a framework to model multiple natural fairness aspects. We seek to find short paths in which the number of occurrences of each color is within some given lower and upper bounds. Among other results, we prove the introduced problems to be computationally intractable (NP-hard and parameterized hard with respect to the number of colors) even in very restricted settings (such as each color should appear with exactly the same frequency), while also presenting an encouraging algorithmic result ("fixed-parameter tractability") related to the length of the sought solution path for the general problem.

ECAI Conference 2023 Conference Paper

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

• Robert Bredereck
• Andrzej Kaczmarczyk 0001
• Dusan Knop
• Rolf Niedermeier

Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter “number of agents” plus “number of item types. ” Our central improvement, compared to their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.

JAIR Journal 2023 Journal Article

Improving Resource Allocations by Sharing in Pairs

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Rolf Niedermeier
• Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to a higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. More precisely, our model allows agents to form pairs which then may share a limited number of resources. Sharing a resource can come at some costs or loss in utility. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

AAAI Conference 2023 Conference Paper

Parameterized Algorithms for Colored Clustering

• Leon Kellerhals
• Tomohiro Koana
• Pascal Kunz
• Rolf Niedermeier

In the Colored Clustering problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent interaction types. More specifically, the goal is to select as many edges as possible without choosing two edges that share an endpoint and are colored differently. Equivalently, the goal can also be described as assigning colors to the vertices in a way that fits the edge-coloring as well as possible. As this problem is NP-hard, we build on previous work by studying its parameterized complexity. We give a 2ᴼ⁽ᵏ⁾·nᴼ⁽¹⁾-time algorithm where k is the number of edges to be selected and n the number of vertices. We also prove the existence of a problem kernel of size O(k⁵ᐟ²), resolving an open problem posed in the literature. We consider parameters that are smaller than k, the number of edges to be selected, and r, the number of edges that can be deleted. Such smaller parameters are obtained by considering the difference between k or r and some lower bound on these values. We give both algorithms and lower bounds for Colored Clustering with such parameterizations. Finally, we settle the parameterized complexity of Colored Clustering with respect to structural graph parameters by showing that it is W[1]-hard with respect to both vertex cover number and tree-cut width, but fixed-parameter tractable with respect to local feedback edge number.

TCS Journal 2023 Journal Article

Temporal interval cliques and independent sets

• Danny Hermelin
• Yuval Itzhaki
• Hendrik Molter
• Rolf Niedermeier

Temporal graphs have been recently introduced to model changes in a given network that occur throughout a fixed period of time. The Temporal Δ Clique problem, which generalizes the well known Clique problem to temporal graphs, has been studied in the context of finding nodes of interest in dynamic networks [TCS '16]. We introduce the Temporal Δ Independent Set problem, a temporal generalization of Independent Set. This problem is e. g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (time-varying) constraints within a given time period. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a certain day if their time-intervals on that day overlap. This leads us to consider both problems on the restricted class of temporal unit interval graphs, i. e. , temporal graphs where each layer is a unit interval graph. We present several hardness results as well as positive results. On the algorithmic side, we provide constant-factor approximation algorithms for instances of both problems where τ, the total number of time steps (layers) of the temporal graph, and Δ, a parameter that allows us to model conflict tolerance, are constants. We develop an exact FPT algorithm for Temporal Δ Clique with respect to parameter τ + k. Finally, we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. For both problems, we provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.

AAMAS Conference 2022 Conference Paper

A Refined Complexity Analysis of Fair Districting over Graphs

• Niclas Boehmer
• Tomohiro Koana
• Rolf Niedermeier

We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into 𝑘 connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).

JAAMAS Journal 2022 Journal Article

A refined complexity analysis of fair districting over graphs

• Niclas Boehmer
• Tomohiro Koana
• Rolf Niedermeier

Abstract We study the NP-hard Fair Connected Districting problem recently proposed by Stoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for “fair districts” without any type being in a dominating majority in any of the districts. This is to e. g. prevent segregation or political domination of some political party. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting. In particular, we prove that it is polynomial-time solvable on paths, cycles, stars, and caterpillars, but already becomes NP-hard on trees. Motivated by the latter negative result, we perform a parameterized complexity analysis with respect to various graph parameters including treewidth, and problem-specific parameters, including, the numbers of colors and districts. We obtain a rich and diverse, close to complete picture of the corresponding parameterized complexity landscape (that is, a classification along the complexity classes FPT, XP, W[1]-hard, and para-NP-hard).

MFCS Conference 2022 Conference Paper

Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems

• Niclas Boehmer
• Klaus Heeger
• Rolf Niedermeier

When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.

AIJ Journal 2022 Journal Article

Envy-free allocations respecting social networks

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist and determining whether they exist is computationally hard even under highly restricted settings. Classical envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since the agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we require that every agent likes its own allocation at least as much as those of all its (out)neighbors. This leads to a “more local” concept of envy-freeness. We also consider a “strong” variant where every agent must like its own allocation more than those of all its (out)neighbors. We analyze the classical and the parameterized complexity of finding allocations that are complete and, at the same time, envy-free with respect to one of the variants of our new concept. To this end, we study different restrictions of the agents' preferences and of the social network structure. We identify cases that become easier (from Σ 2 P -hard or NP-hard to polynomial-time solvable) and cases that become harder (from polynomial-time solvable to NP-hard) when comparing classical envy-freeness with our graph envy-freeness. Furthermore, we spot cases where graph envy-freeness is easier to decide than strong graph envy-freeness, and vice versa. On the route to one of our fixed-parameter tractability results, we also establish a connection to a directed and colored variant of the classical Subgraph Isomorphism problem, thereby extending a known fixed-parameter tractability result for the latter.

AAMAS Conference 2022 Conference Paper

Equilibria in Schelling Games: Computational Hardness and Robustness

• Luca Kreisel
• Niclas Boehmer
• Vincent Froese
• Rolf Niedermeier

In the simplest game-theoretic formulation of Schelling’s model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jumpequilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI ’20] and Elkind et al. [IJCAI ’19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

AAAI Conference 2022 Conference Paper

Modification-Fair Cluster Editing

• Vincent Froese
• Leon Kellerhals
• Rolf Niedermeier

The classic CLUSTER EDITING problem (also known as CORRELATION CLUSTERING) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge modifications. When applied to vertexcolored graphs (the colors representing subgroups), standard algorithms for the NP-hard CLUSTER EDITING problem may yield solutions that are biased towards subgroups of data (e. g. , demographic groups), measured in the number of modifications incident to the members of the subgroups. We propose a modification fairness constraint which ensures that the number of edits incident to each subgroup is proportional to its size. To start with, we study MODIFICATION-FAIR CLUS- TER EDITING for graphs with two vertex colors. We show that the problem is NP-hard even if one may only insert edges within a subgroup; note that in the classic “non-fair” setting, this case is trivially polynomial-time solvable. However, in the more general editing form, the modification-fair variant remains fixed-parameter tractable with respect to the number of edge edits. We complement these and further theoretical results with an empirical analysis of our model on real-world social networks where we find that the price of modification-fairness is surprisingly low, that is, the cost of optimal modification-fair differs from the cost of optimal “non-fair” solutions only by a small percentage.

AAAI Conference 2022 Conference Paper

On Improving Resource Allocations by Sharing

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Rolf Niedermeier
• Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and treelike (hierarchical) social networks.

I&C Journal 2022 Journal Article

Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

• Robert Bredereck
• Klaus Heeger
• Dušan Knop
• Rolf Niedermeier

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). Moreover, we obtain that ‘only’ asking for perfect stable matchings or the mere existence of a stable matching is fixed-parameter tractable with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.

JAIR Journal 2022 Journal Article

The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

• Vincent Froese
• Christoph Hertrich
• Rolf Niedermeier

Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps and complementing results from the literature, we present several results on the parameterized complexity of training two-layer ReLU networks with respect to various loss functions. After a brief discussion of other parameters, we focus on analyzing the influence of the dimension d of the training data on the computational complexity. We provide running time lower bounds in terms of W[1]-hardness for parameter d and prove that known brute-force strategies are essentially optimal (assuming the Exponential Time Hypothesis). In comparison with previous work, our results hold for a broad(er) range of loss functions, including lp-loss for all p ∈ [0, ∞]. In particular, we improve a known polynomial-time algorithm for constant d and convex loss functions to a more general class of loss functions, matching our running time lower bounds also in these cases.

TCS Journal 2022 Journal Article

The structural complexity landscape of finding balance-fair shortest paths

• Matthias Bentert
• Leon Kellerhals
• Rolf Niedermeier

We study the parameterized complexity of finding shortest s-t-paths with an additional fairness requirement. The task is to compute a shortest path in a vertex-colored graph where each color appears (roughly) equally often in the solution. We provide an almost complete picture of the parameterized complexity landscape of the problem with respect to structural parameters by showing a tetrachotomy including polynomial kernels, fixed-parameter tractability, XP-time algorithms (and W [ 1 ] -hardness), and para-NP-hardness.

AAAI Conference 2022 Conference Paper

Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets

• Niclas Boehmer
• Klaus Heeger
• Rolf Niedermeier

Following up on purely theoretical work, we contribute further theoretical insights into adapting stable two-sided matchings to change. Moreover, we perform extensive empirical studies hinting at numerous practically useful properties. Our theoretical extensions include the study of new problems (that is, incremental variants of ALMOST STABLE MARRIAGE and HOSPITAL RESIDENTS), focusing on their (parameterized) computational complexity and the equivalence of various change types (thus simplifying algorithmic and complexitytheoretic studies for various natural change scenarios). Our experimental findings reveal, for instance, that allowing the new matching to be blocked by a few pairs significantly decreases the difference between the old and the new matching.

IJCAI Conference 2022 Conference Paper

Understanding Distance Measures Among Elections

• Niclas Boehmer
• Piotr Faliszewski
• Rolf Niedermeier
• Stanisław Szufa
• Tomasz Wąs

Motivated by putting empirical work based on (synthetic) election data on a more solid mathematical basis, we analyze six distances among elections, including, e. g. , the challenging-to-compute but very precise swap distance and the distance used to form the so-called map of elections. Among the six, the latter seems to strike the best balance between its computational complexity and expressiveness.

AAAI Conference 2021 Conference Paper

A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem

• Matthias Bentert
• Robert Bredereck
• Péter Györgyi
• Andrzej Kaczmarczyk
• Rolf Niedermeier

The NP-hard MATERIAL CONSUMPTION SCHEDULING PROBLEM and related problems have been thoroughly studied since the 1980’s. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewable resources. We focus on the singlemachine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary pre-condition for processing further jobs, each of which having individual resource demands. We initiate a systematic exploration of the parameterized computational complexity landscape of the problem, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the computational complexity. Thereby, we get a deepened understanding of this fundamental scheduling problem.

JAIR Journal 2021 Journal Article

Bribery and Control in Stable Marriage

• Niclas Boehmer
• Robert Bredereck
• Klaus Heeger
• Rolf Niedermeier

We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter "budget" (that is, the number of manipulative actions one is allowed to perform), we also conduct a parameterized complexity analysis and encounter mostly parameterized hardness results.

AAMAS Conference 2021 Conference Paper

Broadening the Research Agenda for Computational Social Choice: Multiple Preference Profiles and Multiple Solutions

• Niclas Boehmer
• Rolf Niedermeier

The area of computational social choice (COMSOC) analyzes collective decision problems from an algorithmic perspective. So far, the main focus in this area lied on analyzing problems where a single preference relation for each agent is given and a single solution reflecting all agents’ preferences needs to be found. However, this modeling is often not rich enough to capture the changing and ambivalent nature of real-world problems. We will argue that one possibility to incorporate such aspects is to allow for multiple preference profiles in the input and multiple solutions in the output. We systematically review different types of arising settings, point out how classical problems and solution concepts can be generalized, and identify several research challenges.

AAAI Conference 2021 Conference Paper

Equitable Scheduling on a Single Machine

• Klaus Heeger
• Dan Hermelin
• George B. Mertzios
• Hendrik Molter
• Rolf Niedermeier
• Dvir Shabtay

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.

AAMAS Conference 2021 Conference Paper

High-Multiplicity Fair Allocation Made More Practical

• Robert Bredereck
• Aleksander Figiel
• Andrzej Kaczmarczyk
• Dušan Knop
• Rolf Niedermeier

The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC 2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for “high-multiplicity fair allocation”, exploiting parameters such as number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We “engineer” their work towards practical usefulness, thereby being able to solve all realworld instances from the state-of-art online platform “spliddit. org for provably fair solutions”. Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e. g. , allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain “solution paths” which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.

IJCAI Conference 2021 Conference Paper

Interference-free Walks in Time: Temporally Disjoint Paths

• Nina Klobas
• George B. Mertzios
• Hendrik Molter
• Rolf Niedermeier
• Philipp Zschoche

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. On the one extreme, we show that on general graphs the problem is computationally hard. The "walk version" is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time solvable for any constant number of walks. The "path version" remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.

TCS Journal 2021 Journal Article

Multistage graph problems on a global budget

• Klaus Heeger
• Anne-Sophie Himmel
• Frank Kammer
• Rolf Niedermeier
• Malte Renken
• Andrej Sajenko

Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as Vertex Cover turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as Matching. In addition to time complexity, we also analyze the space efficiency of our algorithms.

JAAMAS Journal 2021 Journal Article

On coalitional manipulation for multiwinner elections: shortlisting

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

Abstract Shortlisting of candidates—selecting a group of “best” candidates—is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario, \(\ell \) -Bloc (every voter approves \(\ell \) candidates). In particular, we investigate the influence of several different group evaluation functions (e. g. , egalitarian versus utilitarian) and tie-breaking mechanisms modeling pessimistic and optimistic manipulators. Among other things, we conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we provide a fairly comprehensive picture of the computational complexity landscape of this scenario.

IJCAI Conference 2021 Conference Paper

Putting a Compass on the Map of Elections

• Niclas Boehmer
• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Stanisław Szufa

In their AAMAS 2020 paper, Szufa et al. presented a "map of elections" that visualizes a set of 800 elections generated from various statistical cultures. While similar elections are grouped together on this map, there is no obvious interpretation of the elections' positions. We provide such an interpretation by introducing four canonical “extreme” elections, acting as a compass on the map. We use them to analyze both a dataset provided by Szufa et al. and a number of real-life elections. In effect, we find a new parameterization of the Mallows model, based on measuring the expected swap distance from the central preference order, and show that it is useful for capturing real-life scenarios.

AIJ Journal 2021 Journal Article

Robustness among multiwinner voting rules

• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Rolf Niedermeier
• Piotr Skowron
• Nimrod Talmon

We investigate how robust the results of committee elections are with respect to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member might be replaced, or (2) it is possible that the whole committee will be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically NP-hard, but there are natural FPT algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.

IJCAI Conference 2021 Conference Paper

Two Influence Maximization Games on Graphs Made Temporal

• Niclas Boehmer
• Vincent Froese
• Julia Henkel
• Yvonne Lasars
• Rolf Niedermeier
• Malte Renken

To address the dynamic nature of real-world networks, we generalize competitive diffusion games and Voronoi games from static to temporal graphs, where edges may appear or disappear over time. This establishes a new direction of studies in the area of graph games, motivated by applications such as influence spreading. As a first step, we investigate the existence of Nash equilibria in competitive diffusion and Voronoi games on different temporal graph classes. Even when restricting our studies to temporal paths and cycles, this turns out to be a challenging undertaking, revealing significant differences between the two games in the temporal setting. Notably, both games are equivalent on static paths and cycles. Our two main technical results are (algorithmic) proofs for the existence of Nash equilibria in temporal competitive diffusion and temporal Voronoi games when the edges are restricted not to disappear over time.

IJCAI Conference 2021 Conference Paper

Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments

• Niclas Boehmer
• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier

We study the parameterized complexity of counting variants of Swap- and Shift-Bribery, focusing on the parameterizations by the number of swaps and the number of voters. Facing several computational hardness results, using sampling we show experimentally that Swap-Bribery offers a new approach to the robustness analysis of elections.

AAAI Conference 2020 Conference Paper

Adapting Stable Matchings to Evolving Preferences

• Robert Bredereck
• Jiehua Chen
• Dušan Knop
• Junjie Luo
• Rolf Niedermeier

Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of STABLE MARRIAGE and STABLE ROOMMATES. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of INCREMENTAL STA- BLE MARRIAGE and INCREMENTAL STABLE ROOMMATES. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference pro- file) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

AAAI Conference 2020 Conference Paper

Electing Successive Committees: Complexity and Algorithms

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

We introduce successive committees elections. The point is that our new model additionally takes into account that “committee members” shall have a short term of office possibly over a consecutive time period (e. g. , to limit the influence of elitist power cartels or to keep the social costs of overloading committees as small as possible) but at the same time overly frequent elections are to be avoided (e. g. , for the sake of long-term planning). Thus, given voter preferences over a set of candidates, a desired committee size, a number of committees to be elected, and an upper bound on the number of committees that each candidate can participate in, the goal is to find a “best possible” series of committees representing the electorate. We show a sharp complexity dichotomy between computing series of committees of size at most two (mostly in polynomial time) and of committees of size at least three (mostly NP-hard). Depending on the voting rule, however, even for larger committee sizes we can spot some tractable cases.

TCS Journal 2020 Journal Article

Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting

• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Piotr Skowron
• Nimrod Talmon

A classic result of Lenstra [Math. Oper. Res. 1983] says that an integer linear program can be solved in fixed-parameter tractable ( FPT ) time for the parameterization by the number of variables. We extend this result by incorporating piecewise linear convex or concave functions to our (mixed) integer programs. This general technique allows us to analyze the parameterized complexity of a number of classic NP -hard computational problems. In particular, we prove that Weighted Set Multicover is in FPT when parameterized by the number of elements to cover, and that there exists an FPT -time approximation scheme for Multiset Multicover for the same parameter—this is our most technical result. Further, we use our general technique to prove that a number of problems from computational social choice (e. g. , problems related to bribery and control in elections) are in FPT when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems, and for weighted electoral control of Approval voting, this improves some previously known XP -memberships to FPT -memberships.

AAAI Conference 2020 Conference Paper

Parameterized Algorithms for Finding a Collective Set of Items

• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Dušan Knop
• Rolf Niedermeier

We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.

JAAMAS Journal 2020 Journal Article

Stable roommates with narcissistic, single-peaked, and single-crossing preferences

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier

Abstract The classical Stable Roommates problem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigate Stable Roommates with complete (i. e. , every agent can be matched with any other agent) or incomplete preferences, with ties (i. e. , two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms for Stable Roommates that are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity— Stable Roommates remains NP-complete.

TCS Journal 2020 Journal Article

Temporal graph classes: A view through temporal separators

• Till Fluschnik
• Hendrik Molter
• Rolf Niedermeier
• Malte Renken
• Philipp Zschoche

We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal ( s, z ) -Separation problem is NP-complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.

IJCAI Conference 2019 Conference Paper

An Experimental View on Committees Providing Justified Representation

• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Rolf Niedermeier

We provide an experimental study of committees that achieve (proportional/extended) justified representation (JR/PJR/EJR). In particular, we ask how many such committees exist and how varied they are in terms of voter satisfaction and coverage. We find that under many natural distributions of preferences a large fraction of randomly selected JR committees also provide PJR and EJR. Further, we find that the sets of JR committees for our elections are very varied and include both high-quality ones and not-so-appealing ones.

AAMAS Conference 2018 Conference Paper

Envy-Free Allocations Respecting Social Networks

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist, and finding them can be a computationally hard task. Classic envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we require that every agent likes its own allocation at least as much as those of all its (out)neighbors. This leads to a “more local” concept of envyfreeness. We also consider a strong variant where every agent must like its own allocation more than those of all its (out)neighbors. We analyze the classic and the parameterized complexity of finding allocations that are envy-free with respect to one of the variants of our new concept, and that either are complete, are Paretoefficient, or optimize the utilitarian social welfare. To this end, we study different restrictions of the agents’ preferences and of the social network structure. We identify cases that become easier (from ΣP 2-hard or NP-hard to P) and cases that become harder (from P to NP-hard) when comparing classic envy-freeness with our graphbased envy-freeness. Furthermore, we spot cases where graph envyfreeness is easier to decide than strong graph envy-freeness, and vice versa.

MFCS Conference 2018 Conference Paper

The Complexity of Finding Small Separators in Temporal Graphs

• Philipp Zschoche
• Till Fluschnik
• Hendrik Molter
• Rolf Niedermeier

Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that pass through arbitrarily many edges per time step (non-strict) and paths that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial-time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores.

JAIR Journal 2017 Journal Article

Elections with Few Voters: Candidate Control Can Be Easy

• Jiehua Chen
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.

IJCAI Conference 2017 Conference Paper

On Coalitional Manipulation for Multiwinner Elections: Shortlisting

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

Shortlisting of candidates—selecting a group of “best” candidates—is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the most natural and simple voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several tie-breaking mechanisms (e. g. pessimistic versus optimistic) and group evaluation functions (e. g. egalitarian versus utilitarian) and conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. We provide a fairly comprehensive picture of the computational complexity landscape of this neglected scenario.

JAIR Journal 2017 Journal Article

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier
• Toby Walsh

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. They work in multiple stages where the result of each stage may influence the result of the next stage. Both procedures proceed according to a given linear order of the alternatives, an agenda. We obtain the following results for both voting procedures: On the one hand, deciding whether one can make a specific alternative win by reporting insincere preferences by the fewest number of voters, the Manipulation problem, or whether there is a suitable ordering of the agenda, the Agenda Control problem, takes polynomial time. On the other hand, our experimental studies with real-world data indicate that most preference profiles cannot be manipulated by only few voters and a successful agenda control is typically impossible. If the voters' preferences are incomplete, then deciding whether an alternative can possibly win is NP-hard for both procedures. Whilst deciding whether an alternative necessarily wins is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive procedure.

TCS Journal 2017 Journal Article

Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs

• Archontia C. Giannopoulou
• George B. Mertzios
• Rolf Niedermeier

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path, that is, given an undirected graph, find a maximum-length path in G. Longest Path is NP-hard in general but known to be solvable in O ( n 4 ) time on n-vertex interval graphs. We show how to solve Longest Path on Interval Graphs, parameterized by vertex deletion number k to proper interval graphs, in O ( k 9 n ) time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value k can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems.

AAAI Conference 2017 Conference Paper

Teams in Online Scheduling Polls: Game-Theoretic Aspects

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier
• Svetlana Obraztsova
• Nimrod Talmon

Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is being used in order to decide upon the exact time of the meeting. Decisions are to be taken during the meeting, therefore each team would like to maximize its relative attendance (i. e. the proportional number of its team members attending the meeting). We introduce a corresponding game, where each team can declare a lower total availability in the scheduling poll in order to improve its relative attendance—the pay-off. We are especially interested in situations where teams can form coalitions. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in a coalition to improve its pay-off. In contrast, we show that deciding whether such a coalition exists is NP-hard. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is coNP-hard if the coalition size is unbounded.

MFCS Conference 2017 Conference Paper

The Power of Linear-Time Data Reduction for Maximum Matching

• George B. Mertzios
• André Nichterlein
• Rolf Niedermeier

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m\sqrt{n}) time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

IJCAI Conference 2016 Conference Paper

Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

• Bernhard Bliem
• Robert Bredereck
• Rolf Niedermeier

We study the problem of finding a Pareto-efficient and envy-free allocation of a set of indivisible resources to a set of agents with monotonic preferences, either dichotomous or additive. Motivated by results of Bouveret and Lang [JAIR 2008], we provide a refined computational complexity analysis by studying the influence of three natural parameters: the number n of agents, the number m of resources, and the number z of different numbers occurring in utility-based preferences of the agents. On the negative side, we show that small values for n and z alone do not significantly lower the computational complexity in most cases. On the positive side, devising fixed-parameter algorithms we show that all considered problems are tractable in case of small m. Furthermore, we develop a fixed-parameter algorithm indicating that the problem with additive preferences becomes computationally tractable in case of small n and small z.

AAAI Conference 2016 Conference Paper

Complexity of Shift Bribery in Committee Elections

• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the (parameterized) complexity of SHIFT BRIBERY for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin–Courant rules, as well as on approximate variants of the Chamberlin–Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be significantly harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin–Courant rule sometimes affects the complexity of SHIFT BRIBERY.

AIJ Journal 2016 Journal Article

H-index manipulation by merging articles: Models, theory, and experiments

• René van Bevern
• Christian Komusiewicz
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

An author's profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles; this may affect the H-index. We analyze the (parameterized) computational complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatibility graph whose edges correspond to plausible merges. Moreover, we consider several different measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles (that is, for compatibility graphs that are cliques), then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only if one merges articles with highly dissimilar titles.

ECAI Conference 2016 Conference Paper

h-Index Manipulation by Undoing Merges

• René van Bevern
• Christian Komusiewicz
• Hendrik Molter
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

The h-index is an important bibliographic measure used to assess the performance of researchers. Van Bevern et al. [Artif. Intel. , to appear] showed that, despite computational worst-case hardness results, substantial manipulation of the h-index of Google Scholar author profiles is possible by merging articles. Complementing this work, we study the opposite operation, the splitting of articles, which is arguably the more natural operation for manipulation and which is also allowed within Google Scholar. We present numerous results on computational complexity (from linear-time algorithms to parameterized computational hardness results) and empirically indicate that at least small improvements of the h-index by splitting merged articles are easily achievable.

JAIR Journal 2016 Journal Article

Large-Scale Election Campaigns: Combinatorial Shift Bribery

• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the set of candidates and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable; specifically, NP-hard, hard in the parameterized sense, and hard to approximate. Nevertheless, we provide parameterized algorithms and approximation algorithms for natural restricted cases.

I&C Journal 2016 Journal Article

Prices matter for the parameterized complexity of shift bribery

• Robert Bredereck
• Jiehua Chen
• Piotr Faliszewski
• André Nichterlein
• Rolf Niedermeier

In the Shift Bribery problem, we are given an election, a preferred candidate p, and a budget. The goal is to ensure p's victory by shifting p higher in some voters' preference orders. However, each such shift request comes at a price and we must not exceed the given budget. We study the parameterized computational complexity of Shift Bribery for a number of parameters and several classes of price functions: For the number of affected voters, Shift Bribery is W [ 2 ] -hard for Borda, Maximin, and Copeland. For the number of positions by which p is shifted in total, the problem is fixed-parameter tractable for Borda and Maximin, and is W [ 1 ] -hard for Copeland. For the budget, the results depend on the price function class. Finally, Shift Bribery tends to be tractable when parameterized by the number of voters, but the results for the number of candidates are more enigmatic.

I&C Journal 2015 Journal Article

A refined complexity analysis of degree anonymization in graphs

• Sepp Hartung
• André Nichterlein
• Rolf Niedermeier
• Ondřej Suchý

Motivated by a strongly growing interest in graph anonymization, we study the NP-hard Degree Anonymity problem asking whether a graph can be made k-anonymous by adding at most a given number of edges. Herein, a graph is k-anonymous if for every vertex in the graph there are at least k − 1 other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi [ACM SIGMOD 2008]; in particular, we show that the heuristic provides optimal solutions if “many” edges need to be added. Based on this, we develop a polynomial-time data reduction yielding a polynomial-size problem kernel for Degree Anonymity parameterized by the maximum vertex degree. In terms of parameterized complexity analysis, this result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy.

TCS Journal 2015 Journal Article

Combinatorial voter control in elections

• Laurent Bulteau
• Jiehua Chen
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

Voter control problems model situations such as an external agent trying to affect the result of an election by adding voters, for example by convincing some voters to vote who would otherwise not attend the election. Traditionally, voters are added one at a time, with the goal of making a distinguished alternative win by adding a minimum number of voters. In this paper, we initiate the study of combinatorial variants of control by adding voters. In our setting, when we choose to add a voter v, we also have to add a whole bundle κ ( v ) of voters associated with v. We study the computational complexity of this problem for two of the most basic voting rules, namely the Plurality rule and the Condorcet rule.

AAAI Conference 2015 Conference Paper

Elections with Few Voters: Candidate Control Can Be Easy

• Jiehua Chen
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the computational complexity of candidate control in elections with few voters (that is, we take the number of voters as a parameter). We consider both the standard scenario of adding and deleting candidates, where one asks if a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding/deleting some candidates, and a combinatorial scenario where adding/deleting a candidate automatically means adding/deleting a whole group of candidates. Our results show that the parameterized complexity of candidate control (with the number of voters as the parameter) is much more varied than in the setting with many voters.

IJCAI Conference 2015 Conference Paper

H-Index Manipulation by Merging Articles: Models, Theory, and Experiments

• Ren
• eacute; van Bevern
• Christian Komusiewicz
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

An author’s profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles, which may affect the H-index. We analyze the parameterized complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatability graph whose edges correspond to plausible merges. Moreover, we consider multiple possible measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles, then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only by merging articles with highly dissimilar titles, which would be easy to discover.

IJCAI Conference 2015 Conference Paper

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier
• Toby Walsh

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. While finding successful manipulations or agenda controls is tractable for both procedures, our real-world experimental results indicate that most elections cannot be manipulated by a few voters and agenda control is typically impossible. If the voter preferences are incomplete, then finding possible winners is NP-hard for both procedures. Whereas finding necessary winners is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive one.

TCS Journal 2015 Journal Article

The complexity of degree anonymization by vertex addition

• Robert Bredereck
• Vincent Froese
• Sepp Hartung
• André Nichterlein
• Rolf Niedermeier
• Nimrod Talmon

Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results.

AAAI Conference 2014 Conference Paper

Prices Matter for the Parameterized Complexity of Shift Bribery

• Robert Bredereck
• Jiehua Chen
• Piotr Faliszewski
• André Nichterlein
• Rolf Niedermeier

In the SHIFT BRIBERY problem, we are given an election (based on preference orders), a preferred candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters’ preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we must not exceed the given budget. We study the parameterized computational complexity of SHIFT BRIBERY with respect to a number of parameters (pertaining to the nature of the solution sought and the size of the election) and several classes of price functions. When we parameterize SHIFT BRIBERY by the number of affected voters, then for each of our voting rules (Borda, Maximin, Copeland) the problem is W[2]-hard. If, instead, we parameterize by the number of positions by which p is shifted in total, then the problem is fixed-parameter tractable for Borda and Maximin, and is W[1]-hard for Copeland. If we parameterize by the budget for the cost of shifting, then the results depend on the price function class. We also show that SHIFT BRIBERY tends to be tractable when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.

MFCS Conference 2013 Conference Paper

A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems

• Vincent Froese
• René van Bevern
• Rolf Niedermeier
• Manuel Sorge

Abstract We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from high-dimensional data such that the resulting instances fulfill a desired property. In parameterized complexity analysis, one seeks to identify relevant problem-specific quantities and tries to determine their influence on the computational complexity of the considered problem. In this paper, for various combinatorial feature selection problems, we identify parameterizations and reveal to what extent these govern computational complexity. We provide tractability as well as intractability results; for example, we show that the Distinct Vectors problem on binary points is polynomial-time solvable if each pair of points differs in at most three dimensions, whereas it is NP-hard otherwise.

TCS Journal 2013 Journal Article

Incremental list coloring of graphs, parameterized by conservation

• Sepp Hartung
• Rolf Niedermeier

Incrementally k -list coloring a graph means that a graph is given by adding vertices step by step, and for each intermediate step we ask for a vertex coloring such that each vertex has one of the colors specified by its associated list containing some of in total k colors. We introduce the “conservative version” of this problem by adding a further parameter c ∈ N specifying the maximum number of vertices to be recolored between two subsequent graphs (differing by one vertex). The “conservation parameter” c models the natural quest for a modest evolution of the coloring in the course of the incremental process instead of performing radical changes. We show that even on bipartite graphs the problem is NP-hard for k ≥ 3 and W[1]-hard for an unbounded number of colors when parameterized by c. In contrast, also on general graphs the problem becomes fixed-parameter tractable with respect to the combined parameter ( k, c ). We prove that the problem has an exponential-size kernel with respect to ( k, c ) and there is no polynomial-size kernel unless NP ⊆ coNP/poly. Furthermore, we investigate the parameterized complexity on various subclasses of perfect graphs. We show fixed-parameter tractability for the combined parameter treewidth and number k of colors. Finally, we provide empirical findings on the practical relevance of our approach in terms of an effective graph coloring heuristic.

JAAMAS Journal 2013 Journal Article

Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation

• Nadja Betzler
• Robert Bredereck
• Rolf Niedermeier

Abstract Kemeny Rank Aggregation is a consensus finding problem important in many areas ranging from classical voting over web search and databases to bioinformatics. The underlying decision problem Kemeny Score is NP-complete even in case of four input rankings to be aggregated into a “median ranking”. We analyze efficient polynomial-time data reduction rules with provable performance bounds that allow us to find even all optimal median rankings. We show that our reduced instances contain at most candidates where \(d_a\) denotes the average Kendall’s tau distance between the input votes. On the theoretical side, this improves a corresponding result for a “partial problem kernel” from quadratic to linear size. In this context we provide a theoretical analysis of a commonly used data reduction. On the practical side, we provide experimental results with data based on web search and sport competitions, e. g. , computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds. Moreover, we perform experiments with randomly generated data based on two random distribution models for permutations.

AAAI Conference 2012 Conference Paper

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

• Robert Bredereck
• Jiehua Chen
• Sepp Hartung
• Rolf Niedermeier
• Ondřej Suchý
• Stefan Kratsch

We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete LOBBYING problem. Herein, given a binary matrix, the columns represent issues to vote on and the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of LOBBYING, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. Moreover, we show non-existence results concerning efficient and effective preprocessing for LOB- BYING and introduce natural variants such as RESTRICTED LOBBYING and PARTIAL LOBBYING.

MFCS Conference 2012 Conference Paper

New Races in Parameterized Algorithmics

• Christian Komusiewicz
• Rolf Niedermeier

Abstract Once having classified an NP-hard problem fixed-parameter tractable with respect to a certain parameter, the race for the most efficient fixed-parameter algorithm starts. Herein, the attention usually focuses on improving the running time factor exponential in the considered parameter, and, in case of kernelization algorithms, to improve the bound on the kernel size. Both from a practical as well as a theoretical point of view, however, there are further aspects of efficiency that deserve attention. We discuss several of these aspects and particularly focus on the search for “stronger parameterizations” in developing fixed-parameter algorithms.

MFCS Conference 2011 Conference Paper

Pattern-Guided Data Anonymization and Clustering

• Robert Bredereck
• André Nichterlein
• Rolf Niedermeier
• Geevarghese Philip

Abstract A matrix M over a fixed alphabet is k -anonymous if every row in M has at least k − 1 identical copies in M. Making a matrix k -anonymous by replacing a minimum number of entries with an additional ⋆-symbol (called “suppressing entries”) is known to be NP-hard. This task arises in the context of privacy-preserving publishing. We propose and analyze the computational complexity of an enhanced anonymization model where the user of the k -anonymized data may additionally “guide” the selection of the candidate matrix entries to be suppressed. The basic idea is to express this by means of “pattern vectors” which are part of the input. This can also be interpreted as a sort of clustering process. It is motivated by the observation that the “value” of matrix entries may significantly differ, and losing one (by suppression) may be more harmful than losing the other, which again may very much depend on the intended use of the anonymized data. We show that already very basic special cases of our new model lead to NP-hard problems while others allow for (fixed-parameter) tractability results.

IJCAI Conference 2011 Conference Paper

Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

• Nadja Betzler
• Rolf Niedermeier
• Gerhard J. Woeginger

The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of Unweighted Coalitional Manipulation under Borda: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.

AAAI Conference 2010 Conference Paper

Exact Algorithms and Experiments for Hierarchical Tree Clustering

• Sepp Hartung
• Jiong Guo
• Christian Komusiewicz
• Rolf Niedermeier
• Johannes Uhlmann

We perform new theoretical as well as first-time experimental studies for the NP-hard problem to find a closest ultrametric for given dissimilarity data on pairs. This is a central problem in the area of hierarchical clustering, where so far only polynomial-time approximation algorithms were known. In contrast, we develop efficient preprocessing algorithms (known as kernelization in parameterized algorithmics) with provable performance guarantees and a simple search tree algorithm. These are used to find optimal solutions. Our experiments with synthetic and biological data show the effectiveness of our algorithms and demonstrate that an approximation algorithm due to Ailon and Charikar [FOCS 2005] often gives (almost) optimal solutions.

I&C Journal 2010 Journal Article

Parameterized computational complexity of Dodgson and Young elections

• Nadja Betzler
• Jiong Guo
• Rolf Niedermeier

We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties.

IJCAI Conference 2009 Conference Paper

• Nadja Betzler
• Susanne Hemmann
• Rolf Niedermeier

The POSSIBLE WINNER problem asks whether some distinguished candidate may become the winner of an election when the given incomplete votes are extended into complete ones in a favorable way. POSSIBLE WINNER is NP-complete for common voting rules such as Borda, many other positional scoring rules, Bucklin, Copeland etc. We investigate how three different parameterizations in- fluence the computational complexity of POSSI- BLE WINNER for a number of voting rules. We show fixed-parameter tractability results with respect to the parameter “number of candidates” but intractability results with respect to the parameter “number of votes”. Finally, we derive fixedparameter tractability results with respect to the parameter “total number of undetermined candidate pairs” and identify an interesting polynomial-time solvable special case for Borda.

MFCS Conference 2009 Conference Paper

A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

• Michael R. Fellows
• Jiong Guo
• Hannes Moser
• Rolf Niedermeier

Abstract We investigate the computational complexity of a general “compression task” centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of, given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, to find a better disjoint solution. The complexity of this task is so far lacking a systematic study. We consider a large class of vertex deletion problems on undirected graphs and show that, except for few cases which are polynomial-time solvable, the others are NP-complete. This class includes problems such as Vertex Cover (here the corresponding compression task is decidable in polynomial time) or Undirected Feedback Vertex Set (here the corresponding compression task is NP-complete).

TCS Journal 2009 Journal Article

Fixed-parameter algorithms for Kemeny rankings

• Nadja Betzler
• Michael R. Fellows
• Jiong Guo
• Rolf Niedermeier
• Frances A. Rosamond

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permutation” that is “closest” to the given set of permutations. Unfortunately, the problem is NP-hard. We provide a broad study of the parameterized complexity for computing optimal Kemeny rankings. Besides the three obvious parameters “number of votes”, “number of candidates”, and solution size (called Kemeny score), we consider further structural parameterizations. More specifically, we show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall–Tau distance d a ”. We describe a fixed-parameter algorithm with running time 1 6 ⌈ d a ⌉ ⋅ poly. Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NP-complete in the case of an average range of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP. Finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input.

AAMAS Conference 2009 Conference Paper

How Similarity Helps to Efficiently Compute Kemeny Rankings

• Nadja Betzler
• Michael R. Fellows
• Jiong Guo
• Rolf Niedermeier
• Frances A. Rosamond

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Unfortunately, the problem is NP-hard. We show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall-Tau distance da”. We describe a fixed-parameter algorithm with running time 16 da · poly. Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NPcomplete in case of an average range value of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP.

TCS Journal 2009 Journal Article

Isolation concepts for clique enumeration: Comparison and computational experiments

• Falk Hüffner
• Christian Komusiewicz
• Hannes Moser
• Rolf Niedermeier

We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G n, m, p model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks.

TCS Journal 2009 Journal Article

Isolation concepts for efficiently enumerating dense subgraphs

• Christian Komusiewicz
• Falk Hüffner
• Hannes Moser
• Rolf Niedermeier

In an undirected graph G = ( V, E ), a set of k vertices is called c -isolated if it has less than c ⋅ k outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all c -isolated maximal cliques in O ( 4 c ⋅ c 4 ⋅ | E | ) time. We extend this to enumerating all maximal c -isolated cliques (which are a superset) and improve the running time bound to O ( 2. 8 9 c ⋅ c 2 ⋅ | E | ), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s -plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s -plex is the parameter and a fixed-parameter algorithm for enumerating isolated s -plexes when the parameter describes the degree of isolation.

TCS Journal 2006 Journal Article

Editorial

• Rod Downey
• Mike Langston
• Rolf Niedermeier

TCS Journal 2004 Journal Article

Computing the similarity of two sequences with nested arc annotations

• Jochen Alber
• Jens Gramm
• Jiong Guo
• Rolf Niedermeier

We present exact algorithms for the NP-complete LONGEST COMMON SUBSEQUENCE problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences of length at most n and nested arc structure, one of our algorithms determines (if existent) in O(3. 31 k 1+k 2 ·n) time an arc-preserving subsequence of both sequences, which can be obtained by deleting (together with corresponding arcs) k 1 letters from the first and k 2 letters from the second sequence. A second algorithm shows that (in case of a four letter alphabet) we can find a length l arc-annotated subsequence in O(12 l ·l·n) time. This means that the problem is fixed-parameter tractable when parameterized by the number of deletions as well as when parameterized by the subsequence length. Our findings complement known approximation results which give a quadratic time factor-2-approximation for the general and polynomial time approximation schemes for restricted versions of the problem. In addition, we obtain further fixed-parameter tractability results for these restricted versions.

MFCS Conference 2004 Invited Paper

Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms

• Rolf Niedermeier

Abstract Problem parameters are ubiquitous. In every area of computer science, we find all kinds of “special aspects” to the problems encountered. Hence, the study of parameterized complexity for computationally hard problems is proving highly fruitful. The purpose of this article is to stir the reader’s interest in this field by providing a gentle introduction to the rewarding field of fixed-parameter algorithms.

MFCS Conference 2001 Conference Paper

Refined Search Tree Technique for DOMINATING SET on Planar Graphs

• Jochen Alber
• Hongbing Fan
• Michael R. Fellows
• Henning Fernau
• Rolf Niedermeier
• Frances A. Rosamond
• Ulrike Stege

Abstract We establish refined search tree techniques for the parameterized DOMINATING SET problem on planar graphs. We derive a fixed parameter algorithm with running time O(8 k n), where k is the size of the dominating set and n is the number of vertices in the graph. For our search tree, we firstly provide a set of reduction rules. Secondly, we prove an intricate branching theorem based on the Euler formula. In addition, we give an example graph showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final algorithm is very easy (to implement); its analysis, however, is involved.

MFCS Conference 1999 Conference Paper

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

• Henning Fernau
• Rolf Niedermeier

Abstract The “Constraint Bipartite Vertex Cover” problem (CBVC for short) is: given a bipartite graph G with n vertices and two positive integers k 1, k 2, is there a vertex cover taking at most k1 vertices from one and at most k 2 vertices from the other vertex set of G? CBVC is NP -complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide the first nontrivial so-called “fixed parameter” algorithm for CBVC, running in time \( O(1. 3999^{k_1 + k_2 } + (k_1 + k_2 )n) \). Our algorithm is efficient for small values of k 1 and k 2, as occurring in applications.

TCS Journal 1998 Journal Article

Unambiguous computations and locally definable acceptance types

• Rolf Niedermeier
• Peter Rossmanith

Hertrampf's locally definable acceptance types show that many complexity classes can be defined in terms of polynomial-time bounded NTMs with simple local conditions on the nodes of its computation tree, rather than global concepts like number of accepting paths, etc. We introduce a modification of Hertrampf's locally definable acceptance types which allows to get a larger number of characterizable complexity classes. Among others the newly characterizable classes are UP and MOD Zk P. It is shown how different types of oracle access, e. g. , guarded access, can be characterized by this model. This sheds new light on the discussion on how to access unambiguous computation. We present simple functions that describe precisely objects of current research as the unambiguous oracle, alternation, and promise hierarchies. We exhibit the new class UAP which seems to be an unambiguous analogue of Wagner's ▽P. UAP (and thus ▽P) contains Few and is currently the smallest class known with this property.