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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Parameterized Complexity of Shortest Path with Positive Disjunctive Constraints

  • Susobhan Bandopadhyay,
  • Suman Banerjee,
  • Diptapriyo Majumdar,
  • Fahad Panolan

摘要

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.