Combinatorial Optimization with Cuts in Planar Graphs

• Grant number: 25/06231-1
• Support Opportunities: Scholarships in Brazil - Master
• Start date: September 01, 2025
• End date: February 28, 2027
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Marcel Kenji de Carli Silva
• Grantee: Henri Michel França Oliveira
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 23/03167-5 - Classical, asymptotic, quantum and geometric combinatorics, AP.TEM

Abstract

This is the research project for the Master's student Henri Michel França Oliveira, to becarried out at IME-USP under the supervision of Prof. Marcel K. de Carli Silva, from 01/May/2025to 31/Aug/2027, including a planned research internship abroad (BEPE) at the University ofWaterloo. The goal is to determine if efficient algorithms exist for the fractional cut covering problemin planar graphs. Fractional cut covering, through Fulkerson's antiblocking theory, is the dual of thecelebrated MaxCut problem, and understanding dual problems often provides key insights into theoriginal problems, making them central to combinatorial optimization. The applicant will studyMaxCut through the lens of antiblocking duality, followed by an investigation of efficient algorithmsfor MaxCut in planar graphs - a fundamental class of graphs for which many computationallydifficult problems become efficiently solvable. Building on a recent approximation algorithm forfractional cut covering in general graphs, coauthored by the supervisor, the project aims to determinewhether this problem, like MaxCut, admits efficient algorithms in planar graphs. This investigationwill provide the student with deep expertise in combinatorial optimization, preparing him for doctoralstudies while contributing to our understanding of a fundamental theoretical question. (AU)