Approximation Algorithms for Cut Problems in Graphs

• Grant number: 19/24866-3
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: January 01, 2020
• End date: December 31, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: Esther Calderan Hoffmann
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

Abstract

Cut problems in graphs are those in which we search for a set of edges that, once removed, disconnects certain vertices, fulfulling requirements and specifications of the most diverse scenarios. These problems are quite relevant from both the theoretical difficulty point of view, since many of them are NP-hard problems for which various approximation algorithms are known, as well as the motivation of pratical applications such as distributed computing problems, network vulnerability identification and data clustering.This project goals are to study approximation algorithms for cut problems in graphs, such as the Multiway Cut and the Multicut, to implement and test some of these algorithms, and to write a technical report with the main results studied.This undergraduate research project also aims to introduce the candidate to the area of scientific research and to complement her undergraduate course in computer science, deepening her knowledge in combinatorial optimization, approximation algorithms, and the design and analysis of algorithms.