Author name cluster

André Nichterlein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

AAAI Conference 2022 Conference Paper

Combating Collusion Rings Is Hard but Possible

Niclas Boehmer
Robert Bredereck
André Nichterlein

A recent report of Littmann published in the Communications of the ACM outlines the existence and the fatal impact of collusion rings in academic peer reviewing. We introduce and analyze the problem CYCLE-FREE REVIEWING that aims at finding a review assignment without the following kind of collusion ring: A sequence of reviewers each reviewing a paper authored by the next reviewer in the sequence (with the last reviewer reviewing a paper of the first), thus creating a review cycle where each reviewer gives favorable reviews. As a result, all papers in that cycle have a high chance of acceptance independent of their respective scientific merit. We observe that review assignments computed using a standard Linear Programming approach typically admit many short review cycles. On the negative side, we show that CYCLE-FREE REVIEWING is NP-hard in various restricted cases (i. e. , when every author is qualified to review all papers and one wants to prevent that authors review each other’s or their own papers or when every author has only one paper and is only qualified to review few papers). On the positive side, among others, we show that, in some realistic settings, an assignment without any review cycles of small length always exists. This result also gives rise to an efficient heuristic for computing (weighted) cycle-free review assignments, which we show to be of excellent quality in practice.

PDF Details

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.

Details

TCS Journal 2016 Journal Article

Finding large degree-anonymous subgraphs is hard

Cristina Bazgan
Robert Bredereck
Sepp Hartung
André Nichterlein
Gerhard J. Woeginger

A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k − 1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph k-anonymous either through at most s vertex deletions or through at most s edge deletions; the corresponding problem variants are denoted by Anonym V-Del and Anonym E-Del. We present a variety of hardness results, most of them hold for both problems. The two variants are intractable from the parameterized as well as from the approximation point of view. In particular, we show that both variants remain NP-hard on very restricted graph classes like trees even if k = 2. We further prove that both variants are W[1]-hard with respect to the combined parameter solutions size s and anonymity level k. With respect to approximability, we obtain hardness results showing that neither variant can be approximated in polynomial time within a factor better than n 1 2 (unless P = NP ). Furthermore, for the optimization variants where the solution size s is given and the task is to maximize the anonymity level k, this inapproximability result even holds if we allow a running time of f ( s ) ⋅ n O ( 1 ) for any computable function f. On the positive side, we classify both problem variants as fixed-parameter tractable with respect to the combined parameter solution size s and maximum degree Δ.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

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.

PDF Details

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.

Details