On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917315430318080 |
|---|---|
| author | Bandopadhyay, Susobhan Banerjee, Suman Majumdar, Diptapriyo Panolan, Fahad |
| author_facet | Bandopadhyay, Susobhan Banerjee, Suman Majumdar, Diptapriyo Panolan, Fahad |
| contents | We study the SHORTEST PATH problem with positive disjunctive constraints from the perspective of parameterized complexity. For positive disjunctive constraints, there are certain pair of edges such that any feasible solution must contain at least one edge from every such pair. In this paper, we initiate the study of SHORTEST PATH problem subject to some positive disjunctive constraints the classical version is known to be NP-Complete. Formally, given an undirected graph G = (V, E) with a forcing graph H = (E, F) such that the vertex set of H is same as the edge set of G. The goal is to find a set S of at most k edges from G such that S forms a vertex cover in H and there is a path from s to t in the subgraph of G induced by the edge set S. In this paper, we consider two natural parameterizations for this problem. One natural parameter is the solution size, i.e. k for which we provide a kernel with O(k^5) vertices when both G and H are general graphs. Additionally, when either G or H (but not both) belongs to some special graph classes, we provied kernelization results with O(k^3) vertices . The other natural parameter we consider is structural properties of H, i.e. the size of a vertex deletion set of H to some special graph classes. We provide some fixed-parameter tractability results for those structural parameterizations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_04346 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints Bandopadhyay, Susobhan Banerjee, Suman Majumdar, Diptapriyo Panolan, Fahad Discrete Mathematics Data Structures and Algorithms We study the SHORTEST PATH problem with positive disjunctive constraints from the perspective of parameterized complexity. For positive disjunctive constraints, there are certain pair of edges such that any feasible solution must contain at least one edge from every such pair. In this paper, we initiate the study of SHORTEST PATH problem subject to some positive disjunctive constraints the classical version is known to be NP-Complete. Formally, given an undirected graph G = (V, E) with a forcing graph H = (E, F) such that the vertex set of H is same as the edge set of G. The goal is to find a set S of at most k edges from G such that S forms a vertex cover in H and there is a path from s to t in the subgraph of G induced by the edge set S. In this paper, we consider two natural parameterizations for this problem. One natural parameter is the solution size, i.e. k for which we provide a kernel with O(k^5) vertices when both G and H are general graphs. Additionally, when either G or H (but not both) belongs to some special graph classes, we provied kernelization results with O(k^3) vertices . The other natural parameter we consider is structural properties of H, i.e. the size of a vertex deletion set of H to some special graph classes. We provide some fixed-parameter tractability results for those structural parameterizations. |
| title | On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2309.04346 |