Given an undirected graph with edge weights and a subset R of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. We prove that RPP ...is WK1‐complete parameterized by the number and weight d of edges traversed additionally to the required ones. Thus RPP instances cannot be polynomial‐time compressed to instances of size polynomial in d unless the polynomial‐time hierarchy collapses. In contrast, denoting by b ≤ 2d the number of vertices incident to an odd number of edges of R and by c ≤ d the number of connected components formed by the edges in R, we show how to reduce any RPP instance I to an RPP instance I′ with 2b + O(c/ϵ) vertices in O(n3) time so that any α‐approximate solution for I′ gives an α(1 + ϵ)‐approximate solution for I, for any α ≥ 1 and ϵ > 0. That is, we provide a polynomial‐size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide‐spread benchmark data sets as well as on two real snow plowing instances from Berlin. We also make first steps toward a PSAKS for the parameter c.
Given a graph G = (V, E), two vertices s, t ∈ V, and two integers k, ℓ, the Short Secluded Path problem is to find a simple s‐t‐path with at most k vertices and ℓ neighbors. We study the ...parameterized complexity of the problem with respect to four structural graph parameters: the vertex cover number, treewidth, feedback vertex number, and feedback edge number. In particular, we completely settle the question of the existence of problem kernels with size polynomial in these parameters and their combinations with k and ℓ. We also obtain a 2O(tw) · ℓ2 · n‐time algorithm for n‐vertex graphs of treewidth tw, which yields subexponential‐time algorithms in several graph classes.
We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests ...overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover (1+ε)-approximate solutions for arbitrary ε>0. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for ε=0.02.
The NP-hard Multiple Hitting Set problem is the problem of finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a ...well-known data reduction algorithm due to Weihe, we show a problem kernel for Multiple Hitting Set parameterized by the Dilworth number, a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far unexplored in the context of parameterized complexity theory. Using matrix multiplication, we speed up the algorithm to quadratic sequential time and logarithmic parallel time. We experimentally evaluate our algorithms. By implementing our algorithm on GPUs, we show the feasibility of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Data) architectures.
The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the ...special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with ...multiple matroid constraints. We complement our tractability results by hardness results.
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well-known data ...reduction algorithm due to Weihe, we show a problem kernel for Multiple Hitting Set parameterized by the Dilworth number, a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far unexplored in the context of parameterized complexity theory. Using matrix multiplication, we speed up the algorithm to quadratic sequential time and logarithmic parallel time. We experimentally evaluate our algorithms. By implementing our algorithm on GPUs, we show the feasability of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Date) architectures.
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with ...multiple matroid constraints. We complement our tractability results by hardness results.
The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the ...special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.
Given an undirected graph with edge weights and a subset \(R\) of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of \(R\). We prove ...that RPP is WK1-complete parameterized by the number and cost \(d\) of edges traversed additionally to the required ones. Thus, in particular, RPP instances cannot be polynomial-time compressed to instances of size polynomial in \(d\) unless the polynomial-time hierarchy collapses. In contrast, denoting by \(b\leq 2d\) the number of vertices incident to an odd number of edges of \(R\) and by \(c\leq d\) the number of connected components formed by the edges in \(R\), we show how to reduce any RPP instance \(I\) to an RPP instance \(I'\) with \(2b+O(c/\varepsilon)\) vertices in \(O(n^3)\) time so that any \(\alpha\)-approximate solution for \(I'\) gives an \(\alpha(1+\varepsilon)\)-approximate solution for \(I\), for any \(\alpha\geq 1\) and \(\varepsilon>0\). That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. On instances with few connected components, the number of vertices and required edges is reduced to about \(50\,\%\) at a \(1\,\%\) solution quality loss. We also make first steps towards a PSAKS for the parameter \(c\).
PDF
