The popularity of distributed machine learning applications and hardware training imposes increasingly stringent performance requirements on the interconnecting communication network. A clever scheduling of the computational workload has the potential to greatly improve datacenter resource utilization, by keeping frequently communicating nodes topologically close. A fundamental underlying optimization problem is known as (static) balanced graph partitioning: How to partition a graph (describing a workload) into equally-sized subgraphs (“clusters”) to minimize the number of inter-cluster edges?

We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph G, an integer budget k, and a target density τ_ρ, the task is to determine whether the density (i.e. number of edges divided by number of vertices) of the densest subgraph of G can be reduced to at most τ_ρ by deleting at most k vertices. Our primary focus is on structural graph parameters related to treewidth, as the parameterized complexity of BDVD with respect to treewidth was left as open question by Bazgan et al. [JCSS, 2025]. We resolve this question by showing W[1]-hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply W[1]-hardness with respect to treewidth. We obtain positive results for parameters larger than treedepth and feedback vertex number, namely we show BDVD is in FPT parameterized by the max leaf number or vertex integrity. Under the assumption that the target density τ_ρ is a fixed constant the parameterized complexity landscape of BDVD changes drastically, allowing a fixed-parameter tractable algorithm even for parameters smaller than treewidth, namely cliquewidth. Altogether, our results provide a refined complexity landscape for Bounded Density Vertex Deletion, sharply distinguishing between tractable and intractable parameter regimes under structural parameterizations.

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we consider a given physical network and the measured communication demands between the nodes. Our goal is to augment the given physical network with a matching, so that the shortest path lengths in the augmented network, weighted with the demands, are minimal. We prove that this problem is NP-hard, even if the physical network is a cycle. We then use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching in case that only a few nodes in the network cause almost all the communication. For general real-world communication patterns, we design and evaluate a series of heuristics that can deal with arbitrary graphs as the underlying network structure. Our algorithms are validated experimentally using real-world traces (from e.g., Facebook) of data centers.

Segment Routing is a recent network technology that helps optimizing network throughput by providing finer control over the routing paths. Instead of routing directly from a source to a target, packets are routed via intermediate waypoints. Between consecutive waypoints, the packets are routed according to traditional shortest path routing protocols. Bottlenecks in the network can be avoided by such rerouting, preventing overloading parts of the network. The associated NP-hard computational problem is Segment Routing: Given a network and a set of traffic demands (vertex pairs), the task is to find for each demand pair the placement of a given number of waypoints such that with shortest path routing along these waypoints, all demands are fulfilled without exceeding the capacities of the network. We investigate if special structures of real-world communication networks could be exploited algorithmically. Our results comprise NP-hardness on graphs with constant treewidth even if only one waypoint per demand is allowed. We further exclude (under standard complexity assumptions) the existence of efficient exact algorithms even if we assume a fixed number of waypoints per demand and a “small” amount of traffic demands. We complement these lower bounds with polynomial-time solvable special cases.

International audience

We provide a linear-time computable problem kernel of linear size for Strongly Stable Roommates parameterized by the feedback edge number of the acceptability graph (which encodes which agents may be matched to each other). • A linear problem kernel for Strongly Stable Matching is provided. • Stability of a matching is sensible to vertex/edge deletion. • Introduction of annotated problem version helps to design reduction rules.

We analyze the computational complexity of the following computational problems called Bounded-Density Edge Deletion and Bounded-Density Vertex Deletion : Given a graph G , a budget k and a target density τ ρ , are there k edges ( k vertices) whose removal from G results in a graph where the densest subgraph has density at most τ ρ ? Here, the density of a graph is the number of its edges divided by the number of its vertices. We prove that both problems are polynomial-time solvable on trees and cliques but are NP-complete on planar bipartite graphs and split graphs. From a parameterized point of view, we show that both problems are fixed-parameter tractable with respect to the vertex cover number but W[1]-hard with respect to the solution size. Furthermore, we prove that Bounded-Density Edge Deletion is W[1]-hard with respect to the feedback edge number, demonstrating that the problem remains hard on very sparse graphs.

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we differentiate between a given physical network and the measured communication demands between the nodes. Our goal is to minimize the weighted average shortest path length via matching augmentation, where the weights correspond to the communication frequency of any pair of nodes. We use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching on a ring in case only a few nodes in the network cause almost all the communication. Since the problem is NP-hard, we design and evaluate a series of heuristics that can deal with arbitrary graphs as underlying network structures. We evaluate our heuristics on general real-world communication patterns and show that already with simple and efficient heuristics we are able to reach near-optimal quality.

Finding large "cliquish" subgraphs is a classic NP-hard graph problem. In this work, we focus on finding maximum $s$-clubs and $s$-plexes, i.e., graphs of diameter $s$ and graphs where each vertex is adjacent to all but $s$ vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a new parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we provide evidence that the new theoretical bounds indeed better explain the observed running times than the existing theoretical running time bounds. To this end, we suggest a general method to compare how well theoretical running time bounds fit to measured running times.

We provide a general framework to exclude parameterized running times of the form $O(\ell^β+ n^γ)$ for problems that have polynomial running time lower bounds under hypotheses from fine-grained complexity. Our framework is based on cross-compositions from parameterized complexity. We (conditionally) exclude running times of the form $O(\ell^{γ/{(γ-1)} - ε} + n^γ)$ for any $1<γ<2$ and $ε>0$ for the following problems: - Longest Common Subsequence: Given two length-$n$ strings and $\ell\in\mathbb{N}$, is there a common subsequence of length $\ell$? - Discrete Fréchet Distance: Given two lists of $n$ points each and $k\in \mathbb{N}$, is the Fréchet distance of the lists at most $k$? Here $\ell$ is the maximum number of points which one list is ahead of the other list in an optimum traversal. Moreover, we exclude running times $O(\ell^{{2γ}/{(γ-1)}-ε} + n^γ)$ for any $1<γ<3$ and $ε>0$ for: - Negative Triangle: Given an edge-weighted graph with $n$ vertices, is there a triangle whose sum of edge-weights is negative? Here $\ell$ is the order of a maximum connected component. - Triangle Collection: Given a vertex-colored graph with $n$ vertices, is there for each triple of colors a triangle whose vertices have these three colors? Here $\ell$ is the order of a maximum connected component. - 2nd Shortest Path: Given an $n$-vertex edge-weighted directed graph, two vertices $s$ and $t$, and $k \in \mathbb{N}$, has the second longest $s$-$t$-path length at most $k$? Here $\ell$ is the directed feedback vertex set. Except for 2nd Shortest Path all these running time bounds are tight, that is, algorithms with running time $O(\ell^{γ/{(γ-1)}} + n^γ)$ for any $1 < γ< 2$ and $O(\ell^{{2γ}/{(γ-1)}} + n^γ)$ for any $1 < γ< 3$, respectively, are known.

Abstract Diameter—the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no $$O(n^{1.99})$$ O ( n 1.99 ) -time algorithm even in sparse graphs (Roditty L, Williams, VV in Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC ’13), pp 515–524. ACM, 2013). To circumvent this lower bound, we investigate which parameters allow for running times of the form $$f(k) (n+m)$$ f ( k ) ( n + m ) where k is the respective parameter and f is a computable function. To this end, we systematically explore a hierarchy of structural graph parameters.

Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of a parameter chosen in advance. Kernelization for weighted problems particularly requires to also shrink weights. Marx and V\'egh [ACM Trans. Algorithms 2015] and Etscheid et al. [J. Comput. Syst. Sci. 2017] used a technique of Frank and Tardos [Combinatorica 1987] to obtain polynomial-size kernels for weighted problems, mostly with additive goal functions. We characterize the function types that the technique is applicable to, which turns out to contain many non-additive functions. Using this insight, we systematically obtain kernelization results for natural problems in graph partitioning, network design, facility location, scheduling, vehicle routing, and computational social choice, thereby improving and generalizing results from the literature.

Abstract. Given an undirected [Formula: see text]-vertex graph and [Formula: see text] pairs [Formula: see text] of terminal vertices, the [Formula: see text]-Disjoint Shortest Paths ([Formula: see text]-SDP) problem asks whether there are [Formula: see text] pairwise vertex-disjoint paths [Formula: see text] such that [Formula: see text] is a shortest [Formula: see text]-[Formula: see text]-path for each [Formula: see text]. Recently, Lochet [ Proceedings of the 32 nd ACM-SIAM Symposium on Discrete Algorithms (SODA ’21 ), SIAM, 2021, pp. 169–178] provided an algorithm that solves [Formula: see text]-SDP in [Formula: see text] time, answering a 20-year old question about the computational complexity of [Formula: see text]-SDP for constant [Formula: see text]. On the one hand, we present an improved [Formula: see text]-time algorithm based on a novel geometric view on this problem. For the special case [Formula: see text] on [Formula: see text]-edge graphs, we show that the running time can be further reduced to [Formula: see text] by small modifications of the algorithm and a refined analysis. On the other hand, we show that [Formula: see text]-SDP is W[1]-hard with respect to [Formula: see text], showing that the dependency of the degree of the polynomial running time on the parameter [Formula: see text] is presumably unavoidable.

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.

Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm that, given a problem instance as input, outputs an equivalent, typically smaller instance of the same problem. The application of data reduction rules during the preprocessing of problem instances allows in many cases to considerably shrink their size, or even solve them directly. Commonly, these data reduction rules are applied exhaustively and in some fixed order to obtain irreducible instances. It was often observed that by changing the order of the rules, different irreducible instances can be obtained. We propose to "undo" data reduction rules on irreducible instances, by which they become larger, and then subsequently apply data reduction rules again to shrink them. We show that this somewhat counter-intuitive approach can lead to significantly smaller irreducible instances. The process of undoing data reduction rules is not limited to "rolling back" data reduction rules applied to the instance during preprocessing. Instead, we formulate so-called backward rules, which essentially undo a data reduction rule, but without using any information about which data reduction rules were applied to it previously. In particular, based on the example of Vertex Cover we propose two methods applying backward rules to shrink the instances further. In our experiments we show that this way smaller irreducible instances consisting of real-world graphs from the SNAP and DIMACS datasets can be computed.

We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed $α$ between zero and one we are given a graph and two numbers $k \in \mathbb{N}$ and $t \in \mathbb{Q}$. The task is to find a vertex subset $S$ of exactly $k$ vertices that has value at least (resp. at most for minimization) $t$. Here, the value of a vertex set computes as $α$ times the number of edges with exactly one endpoint in $S$ plus $1-α$ times the number of edges with both endpoints in $S$. These two problems generalize many prominent graph problems, such as Densest $k$-Subgraph, Sparsest $k$-Subgraph, Partial Vertex Cover, and Max ($k$,$n-k$)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max $(k,n-k)$-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.

We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show that under the exponential time hypothesis, there are no exact algorithms running in 2o(n) time or in [Formula: see text] time for any computable function f. We also show that the special case of connecting c network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size cO(1) unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects O(log n)-connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c. Summary of Contribution: Wireless sensor networks are used to monitor air pollution, water pollution, and machine health; in forest fire and landslide detection; and in natural disaster prevention. Sensors in wireless sensor networks are often battery-powered and disposable, so one may be interested in lowering the energy consumption of the sensors in order to achieve a long lifetime of the network. We study the min-power symmetric connectivity problem, which models the task of assigning transmission powers to sensors so as to achieve a connected communication network with minimum total power consumption. The problem is NP-hard. We provide perhaps the first parameterized complexity study of optimal and approximate solutions for the problem. Our algorithms work in polynomial time in the scenario where one has to reconnect a sensor network with n sensors and O(log n)-connected components by means of a minimum transmission power increase or if one can find transmission power lower bounds that already yield a network with O(log n)-connected components. In experiments, we show that, in this scenario, our algorithms outperform previously known exact algorithms based on ILP formulations.

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter at most two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the editing operations are vertex deletions). Answering an open question, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then, focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, outperforming a standard CPLEX solver in most instances of an established biological test data set.

Given an undirected $n$-vertex graph and $k$ pairs of terminal vertices $(s_1,t_1), \ldots, (s_k,t_k)$, the $k$-Disjoint Shortest Paths ($k$-DSP)-problem asks whether there are $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i \in [k]$. Recently, Lochet [SODA 2021] provided an algorithm that solves $k$-DSP in $n^{O(k^{5^k})}$ time, answering a 20-year old question about the computational complexity of $k$-DSP for constant $k$. On the one hand, we present an improved $n^{O(k!k)}$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$ on $m$-edge graphs, we show that the running time can be further reduced to $O(nm)$ by small modifications of the algorithm and a refined analysis. On the other hand, we show that $k$-DSP is W[1]-hard with respect to $k$, showing that the dependency of the degree of the polynomial running time on the parameter $k$ is presumably unavoidable.

The Parameterized Algorithms and Computational Experiments challenge (PACE) 2021 was devoted to engineer algorithms solving the NP-hard Cluster Editing problem, also known as Correlation Clustering: Given an undirected graph the task is to compute a minimum number of edges to insert or remove in a way that the resulting graph is a cluster graph, that is, a graph in which each connected component is a clique. Altogether 67 participants from 21 teams, 11 countries, and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances, and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers.

Abstract We introduce a dynamic version of the -hard graph modification problemCluster Editing. The essential point here is to take into account dynamically evolving input graphs: having a cluster graph (that is, a disjoint union of cliques) constituting a solution for a first input graph, can we cost-efficiently transform it into a “similar” cluster graph that is a solution for a second (“subsequent”) input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (three modification scenarios edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as (parameterized) hardness results, thus (except for three open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the two perhaps most natural parameterizations: the distances of the new “similar” cluster graph to (1) the second input graph and to (2) the input cluster graph.

A Correction to this paper has been published: https://doi.org/10.1007/s00224-021-10057-6

Abstract 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})$$ O ( m 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.

Abstract We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.

There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, we develop a general two-stage framework which consists of efficiently solving a problem-specific number problem and transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while f -factor computations as used in the undirected case seem not to work for the directed case.

Abstract We study the NP‐hard shortest path most vital edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest st‐path as much as possible. This scenario has been studied from the viewpoint of parameterized complexity and approximation algorithms. We contribute to this line of research by providing refined computational tractability as well as hardness results. We achieve this by a systematic investigation of various problem‐specific parameters and their influence on the computational complexity. Charting the border between tractability and intractability, we also identify numerous challenges for future research.

Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For n-vertex and m-edge graphs, the best known algorithms run in O~(m sqrt{n}) time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) linear-time data reduction rules for the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementation for computing matchings in real-world graphs: the average speedup is 3800% in the unweighted case and "just" 30% in the weighted case.

We introduce a dynamic version of the NP-hard Cluster Editing problem. The essential point here is to take into account dynamically evolving input graphs: Having a cluster graph (that is, a disjoint union of cliques) that represents a solution for a first input graph, can we cost-efficiently transform it into a "similar" cluster graph that is a solution for a second ("subsequent") input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as parameterized hardness results, thus (except for two open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the perhaps two most natural parameterizations: the distance of the new "similar" cluster graph to (i) the second input graph and to (ii) the input cluster graph.

Betweenness centrality - measuring how many shortest paths pass through a vertex - is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [2001] computes, on an n-vertex and m-edge graph, the betweenness centrality of all vertices in O(nm) worst-case time. In follow-up work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We further contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound O(kn), where k < m is the size of a minimum feedback edge set of the input graph.

The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos [ Discrete Optim., 8 (2011), pp. 77--86], we show that, unless ${NP}\subseteq {{coNP}}/{{poly}}$, the NP-hard Length-Bounded Edge-Cut (LBEC) problem (delete at most $k$ edges such that the resulting graph has no $s$-$t$ path of length shorter than $\ell$) parameterized by the combination of $k$ and $\ell$ has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex-deletion problems. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general $m$-edge and $n$-vertex graphs, it is well known to be solvable in $O(m\sqrt{n})$ time. We present a linear-time algorithm to find maximum-cardinality matchings on cocomparability graphs, a prominent subclass of perfect graphs that strictly contains interval graphs as well as permutation graphs. Our greedy algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS).

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.

Bodlaender et al.'s [Bodlaender/Jansen/Kratsch,2014] cross-composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of cross-compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. Roughly speaking, our new technique combines the advantages of serial and parallel composition. In particular, answering an open question of Golovach and Thilikos [Golovach/Thilikos,2011], we show that, unless NP subseteq coNP/poly, the NP-hard Length-Bounded Edge-Cut problem (delete at most k edges such that the resulting graph has no s-t path of length shorter than l) parameterized by the combination of k and l has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex deletion problems.

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$.

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.

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.