Exact Algorithms for Edge Covering Problems with Paths

• Grant number: 22/15408-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: March 01, 2023
• End date: November 30, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Rafael Crivellari Saliba Schouery
• Grantee: Bernardo Panka Archegas
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

The Minimum Path-Collection Exact Cover (PCEC) is a problem where, given a directed graph G and a set of paths of G, it is necessary to find the subset of paths of lowest cardinality such that every edge of the graph is covered exactly once . The Minimum k-Path Splitting Exact Cover (k-PSEC) is a variant of the PCEC in which there are restrictions on the chosen paths. These problems belong to the NP-hard class, that is, there are no algorithms that solve them exactly in polynomial time, unless P = NP. However, it is still possible to search for exact algorithms for NP-hard problems that are efficient in practice, with great advances in this regard in the literature in recent decades. In this project, we will develop exact algorithms for PCEC and k-PSEC, using techniques such as Branch and Bound and Dynamic Programming. Furthermore, the project also aims to introduce the candidate to the field of scientific research and complement his formation.