On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917893874122752 |
|---|---|
| author | Tellache, Nour ElHouda Baldacci, Roberto |
| author_facet | Tellache, Nour ElHouda Baldacci, Roberto |
| contents | The Minimum Path Cover (MPC) problem consists of finding a minimum-cardinality set of node-disjoint paths that cover all nodes in a given graph. We explore a variant of the MPC problem on acyclic digraphs (DAGs) where, given a subset of arcs, each path within the MPC should contain at least one arc from this subset. We prove that the feasibility problem is strongly NP-hard on arbitrary DAGs, but the problem can be solved in polynomial time when the DAG is the transitive closure of a path.
Given that the problem may not always be feasible, our solution focuses on covering a maximum number of nodes with a minimum number of node-disjoint paths, such that each path includes at least one arc from the predefined subset of arcs. This paper introduces and investigates two integer programming formulations for this problem. We propose several valid inequalities to enhance the linear programming relaxations, employing them as cutting planes in a branch-and-cut approach. The procedure is implemented and tested on a wide range of instances, including real-world instances derived from an airline crew scheduling problem, demonstrating the effectiveness of the proposed approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_09560 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method Tellache, Nour ElHouda Baldacci, Roberto Discrete Mathematics Optimization and Control The Minimum Path Cover (MPC) problem consists of finding a minimum-cardinality set of node-disjoint paths that cover all nodes in a given graph. We explore a variant of the MPC problem on acyclic digraphs (DAGs) where, given a subset of arcs, each path within the MPC should contain at least one arc from this subset. We prove that the feasibility problem is strongly NP-hard on arbitrary DAGs, but the problem can be solved in polynomial time when the DAG is the transitive closure of a path. Given that the problem may not always be feasible, our solution focuses on covering a maximum number of nodes with a minimum number of node-disjoint paths, such that each path includes at least one arc from the predefined subset of arcs. This paper introduces and investigates two integer programming formulations for this problem. We propose several valid inequalities to enhance the linear programming relaxations, employing them as cutting planes in a branch-and-cut approach. The procedure is implemented and tested on a wide range of instances, including real-world instances derived from an airline crew scheduling problem, demonstrating the effectiveness of the proposed approach. |
| title | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2501.09560 |