On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method
<p dir="ltr">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 directed acyclic graphs (DAGs) where, given a subset of arcs, each path within the...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| منشور في: |
2025
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513533175136256 |
|---|---|
| author | Nour ElHouda Tellache (22565366) |
| author2 | Roberto Baldacci (14779375) |
| author2_role | author |
| author_facet | Nour ElHouda Tellache (22565366) Roberto Baldacci (14779375) |
| author_role | author |
| dc.creator.none.fl_str_mv | Nour ElHouda Tellache (22565366) Roberto Baldacci (14779375) |
| dc.date.none.fl_str_mv | 2025-06-16T09:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1002/net.22290 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/On_a_Variant_of_the_Minimum_Path_Cover_Problem_in_Acyclic_Digraphs_Computational_Complexity_Results_and_Exact_Method/30541346 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Engineering Communications engineering Information and computing sciences Software engineering branch-and-cut complexity constrained minimum path cover directed acyclic graphs separation problems valid inequalities |
| dc.title.none.fl_str_mv | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">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 directed acyclic graphs (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 ‐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.</p><h2>Other Information</h2><p dir="ltr">Published in: Networks<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1002/net.22290" target="_blank">https://dx.doi.org/10.1002/net.22290</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_35b840aac45f03b89de312a43bee17cf |
| identifier_str_mv | 10.1002/net.22290 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/30541346 |
| publishDate | 2025 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact MethodNour ElHouda Tellache (22565366)Roberto Baldacci (14779375)EngineeringCommunications engineeringInformation and computing sciencesSoftware engineeringbranch-and-cutcomplexityconstrained minimum path coverdirected acyclic graphsseparation problemsvalid inequalities<p dir="ltr">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 directed acyclic graphs (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 ‐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.</p><h2>Other Information</h2><p dir="ltr">Published in: Networks<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1002/net.22290" target="_blank">https://dx.doi.org/10.1002/net.22290</a></p>2025-06-16T09:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1002/net.22290https://figshare.com/articles/journal_contribution/On_a_Variant_of_the_Minimum_Path_Cover_Problem_in_Acyclic_Digraphs_Computational_Complexity_Results_and_Exact_Method/30541346CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/305413462025-06-16T09:00:00Z |
| spellingShingle | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method Nour ElHouda Tellache (22565366) Engineering Communications engineering Information and computing sciences Software engineering branch-and-cut complexity constrained minimum path cover directed acyclic graphs separation problems valid inequalities |
| status_str | publishedVersion |
| title | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| title_full | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| title_fullStr | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| title_full_unstemmed | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| title_short | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| title_sort | On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method |
| topic | Engineering Communications engineering Information and computing sciences Software engineering branch-and-cut complexity constrained minimum path cover directed acyclic graphs separation problems valid inequalities |