In graph realization problems, one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrast, we show NP-completeness for the problem of realizing a given sequence of pairs of nonnegative integers (representing in- and outdegrees) with a directed acyclic graph (DAG), answering an open question of Berger and Müller-Hannemann. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter “maximum degree.” Investigating sparse and dense settings, we show that the problem remains NP-hard even if the realizing DAG (precisely, the underlying undirected graph) can be transformed into a clique (a tree) by adding (deleting) a constant fraction of the arcs. In contrast, if at most $k$ arcs have to be inserted, respectively, removed to obtain a clique or a tree in the underlying undirected graph, then the problem becomes fixed-parameter tractable with respect to $k$.

Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard Lobbying problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the "maximum number of 1s missing for any column to have a majority of 1s" (referred to as "gap value g") govern the computational complexity of Lobbying. Among other results, we prove that Lobbying is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves Lobbying even optimally if m < 5. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that Lobbying is LOGSNP-complete for constant values g>0, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.

The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in G. Herein, a vertex v separates a pair {u, w} if the distance (length of a shortest path) between v and u is different from the distance of v and w. We give a polynomial-time computable reduction from the Bipartite Dominating Set problem to Metric Dimension on maximum degree three graphs such that there is a one-to-one correspondence between the solution sets of both problems. There are two main consequences of this: First, it proves that Metric Dimension on maximum degree three graphs is W[2]-hard with respect to the parameter k. This answers an open question concerning the parameterized complexity of Metric Dimension posed by Lokshtanov [Dagstuhl seminar, 2009] and also by Diaz et al. [ESA'12]. Additionally, it implies that a trivial nO(k)-time algorithm cannot be improved to an no(k)-time algorithm, unless the assumption FPT≠W[1] fails. Second, as Bipartite Dominating Set is inapproximable within o(log n), it follows that Metric Dimension on maximum degree three graphs is also inapproximable by a factor of o(log n), unless NP=P. This strengthens the result of Hauptmann et al. [JDA'12] who proved APX-hardness on bounded-degree graphs.

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 Lobbying and introduce natural variants such as Restricted Lobbying and Partial Lobbying.

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.