This is the Ph.D. project of Phablo Fernando Soares Moura, to be developed under supervision of Y. Wakabayashi at Instituto de Matemática e Estatística - Universidade de São Paulo.This project falls within the area of combinatorial optimization, and focuses on partitioning problems on graphs under some constraints. One of the problems that will be investigated in this project is the convex recoloring problem. Roughly speaking, the input of this problem is a graph in which the vertices are (arbitrarily) colored, and the objective is minimize the number of color changes so that, for each color in the recoloring, the vertices with this color induce a connected subgraph. Basically, the objective of the recoloring is to partition the vertex set in such a way that each class of the partition induces a connected subgraph.This problem has its origins in the study of phylogenetic trees, but it can be easily extended to more general versions and arbitrary graphs, having been studied under several approaches. It is an NP-hard problem even on paths.We propose to investigate more general versions of this problem on arbitrary graphs, with focus on the study of different integer linear formulations, the relation between such formulations and algorithmic aspects.
News published in Agência FAPESP Newsletter about the scholarship: