Optimization problems on graph partitioning

• Grant number: 13/19179-0
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: December 01, 2013
• End date: March 31, 2017
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Phablo Fernando Soares Moura
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated scholarship(s): 15/11930-4 - Graph partitioning problems, BE.EP.DR

Abstract

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.

Scientific publications

(4)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

COELHO, RAFAEL S.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The k-hop connected dominating set problem: approximation and hardness. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 34, n. 4, p. 1060-1083, NOV 2017. (13/03447-6, 15/11930-4, 13/19179-0)

ABOULKER, PIERRE; COHEN, NATHANN; HAVET, FREDERIC; LOCHET, WILLIAM; MOURA, PHABLO F. S.; THOMASSE, STEPHAN. Subdivisions in digraphs of large out-degree or large dichromatic number. ELECTRONIC JOURNAL OF COMBINATORICS, v. 26, n. 3, JUL 19 2019. (15/11930-4, 16/21250-3, 17/22611-2, 13/19179-0)

CAMPELO, MANOEL; MOURA, PHABLO F. S.; SANTOS, MARCIO C.. Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope. DISCRETE OPTIMIZATION, v. 21, p. 131-156, AUG 2016. (13/03447-6, 15/11930-4, 13/19179-0)

CAMPELO, MANOEL; FREIRE, ALEXANDRE S.; LIMA, KARLA R.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The convex recoloring problem: polyhedra, facets and computational experiments. MATHEMATICAL PROGRAMMING, v. 156, n. 1-2, p. 303-330, MAR 2016. (13/03447-6, 13/19179-0, 12/17585-9)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

MOURA, Phablo Fernando Soares. Graph colorings and digraph subdivisions. 2017. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.