ﻻ يوجد ملخص باللغة العربية
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 WK[1]-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 $bleq 2d$ the number of vertices incident to an odd number of edges of $R$ and by $cleq 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 $alphageq 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$.
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 o
Given a graph $G=(V,E)$, two vertices $s,tin V$, and two integers $k,ell$, the Short Secluded Path problem is to find a simple $s$-$t$-path with at most $k$ vertices and $ell$ neighbors. We study the parameterized complexity of the problem with respe
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
Recent work has shown that many problems of satisfiability and resiliency in workflows may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and No otherwise. However,
The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundamental combinatorial problem and has received extensive attention in va