Parameterized Complexity of Shortest Path with Positive Disjunctive Constraints
摘要
We study the Shortest Path problem subject to positive binary disjunctive constraints. In positive disjunctive constraints, there are certain pairs of edges such that at least one edge from every pair must be part of every feasible solution. We initiate the study of Shortest Path with binary positive disjunctive constrains from the perspective of parameterized complexity. Formally, the input instance is a simple unidirected graph \(G = (V, E)\) , a forcing graph \(G_f = (E, E')\) , two vertices \(s, t \in V(G)\) and an integer k. Note that the vertex set of \(G_f\) is the same as the edge set of G. The goal is to find a set S of at most k edges from G such that there is a path from s to t in the subgraph \(G = (V, S)\) and S is a vertex cover in \(G_{f}\) . In this paper, we consider two different natural parameterizations for this problem. One natural parameter is the solution size, i.e. k for which we provide FPT algorithms and polynomial kernelization results. The other natural parameters are structural parameterisations of \(G_f\) , i.e. the size of a modulator \(X \subseteq E(G) = V(G_f)\) such that \(G_f - X\) belongs to some hereditary graph class. We discuss the parameterized complexity of this problem under some structural parameterizations.