Among my 119 publications in international refereed journals, I have selected the 10 below covering a number of different topics from graph theory and theoretical computer science, 6 of them exhibit long standing central problems that I solved, 5 of them are product of PhD theses that I supervised, and 1 is a survey of a plenary talk. While several research topics like perfect graphs and the computational complexity hierarchy are visible throughout my entire scientific career, I regularly work on new problems and applications such as bioinformatics and quantum computing. I chose the chronological order that emphasizes the regularity of my production, spread along 30 years after my doctoral degree. Among the 28 co-authors below, 8 PhD students and 8 different nationalities are represented, and 8 leading journals in the area of Theoretical Computer Science and Discrete Applied Mathematics.
This paper gave international visibility to my research work and it is my most cited paper. The Skew Partition defined by Chvátal in 1985 is a key decomposition for the Strong Perfect Graph Theorem proved by Chudnovsky et al. in 2002. This paper gives a polynomial-time algorithm for testing whether a graph admits a skew partition. I presented that algorithm at the Latin American Symposium on Theoretical Informatics in 2000, and published the full paper in the very prestigious Journal of Algorithms, at the time edited by Knuth, Johnson, and Galil. In 2001, I was invited to speak about it at closed workshops in Dagstuhl and Princeton, and in 2004 at a conference in honor of Claude Berge, who defined the area of Perfect Graphs. This paper proves that I have Erdös number 2, since Yoshiharu Kohayakawa is the only Brazilian co-author of Paul Erdös.
This paper on polynomial-time combinatorial algorithms for the optimal weighted coloring and clique problems in bull-free perfect graphs solved the problem Bruce Reed gave me when I was a visiting student at the University of Waterloo in 1989. I met Frédéric Maffray in 1989 at a workshop on perfect graphs and we continuously worked together until his premature death in 2018. We co-authored several papers, coordinated joint Brazil-France projects, and co-supervised four female PhD students. We celebrated our close partnership in a Centenary conference in Grenoble in 2010. Optimizing bull-free perfect graphs was a problem proposed by Chvátal in 1987 as a key step towards a combinatorial algorithm to compute the chromatic number of a perfect graph, a central and still open problem in Graph Theory. Frédéric and I were twice guest speakers, consecutive and complementary, about our journey to color these graphs: at the Fields Institute in 2000 and at Dagstuhl in 2007.
In this paper, my first PhD student Luerbio Faria and I solved the conjecture posed by Erdös in 1973 on the crossing number of the hypercube. Our co-authors are experts in the problem. I met them at WG 1998, the Workshop on Graph-Theoretic Concepts in Computer Science, an important Graph Theory conference. Since then I have been able to continuously participate at WG presenting papers and serving four times as the only Latin American member of its Program Committee. It took us ten years to turn the extended abstract of the WG proceedings into the full paper with Erdös drawings published in the Journal of Graph Theory. In 2014, I gave an invited talk at the Foundations of Computational Mathematics conference about further planarity parameters, which was later also published as a paper in the Journal of Graph Theory.
The time complexity of recognizing clique graphs was a long-standing question open since 1971. I learned about this problem in a survey on clique graphs by my PhD supervisor Jayme Szwarcfiter. In this paper we proved that the clique graph recognition problem is NP-complete. The extended abstract was published in the Graph-Theoretic Concepts in Computer Science proceedings in 2006, which we dedicated to Alberto Santos Dumont, aviation pioneer, on the 100th anniversary of the flight of his 14 Bis in Paris in October 1906. My co-authors in this paper are my first PhD student and most frequent co-author Luerbio Faria, and Marisa Gutierrez and Liliana Alcón from Argentina. They are two key long-term collaborators in the context of two series of Latin American conferences where I belong to the steering committee: the Latin and American Algorithms, Graphs and Optimization Symposium, and the Latin American Workshop on Cliques in Graphs.
This survey paper contains my personal approach to the P versus NP problem. I discuss classes of problems for which dichotomy results do exist: every problem in the class is classified into polynomial or NP-complete, and my contribution through the classification of some long-standing open problems in important areas of graph theory: perfect graphs, intersection graphs, and structural characterization of graph classes. The paper is the journal version of my plenary talk given at LAGOS 2009, the Latin-American Algorithms, Graphs and Optimization Symposium. The P versus NP problem is one of the seven Millennium Problems selected by the Clay Mathematics Institute to motivate research on important classic mathematical questions that have resisted solution over the years. The P versus NP problem is the central problem in theoretical computer science: it aims to classify the possible existence of efficient solutions to combinatorial and optimization problems.
In the study of genome rearrangements, Sorting by Transpositions is an NP-hard problem for which several polynomial-time approximation algorithms have been developed. For developing approximation algorithms, one searches for the optimal trade-off between the quality of the approximation and the running time. The algorithm proposed in this paper achieves the best trade-off by combining all tools published in leading journals by leading researchers, and by correcting a previous publication in the same prestigious Journal of Computational Biology. My co-authors are three former PhD students: two of them did their theses on genome rearrangements in 2007 and 2017; the third one did his thesis on quantum computing in 2006 and was key with his expertise regarding data structures to handle permutation trees. The research projects that I coordinate benefit from the fact that most of my 19 PhD students are research professors at universities in Rio de Janeiro; after finishing their degrees, the young researchers pursue their thesis topics as post-docs, and co-supervising theses with me.
In this paper, we solve an open problem posed by Kratochvíl and Tuza to determine the complexity of 2-clique-colouring of perfect graphs with all cliques having size at least 3, proving that is complete with respect to the third level of the polynomial-time hierarchy. We also determine a hierarchy of nested subclasses of perfect graphs with all cliques having size at least 3 whereby each graph class is in a distinct complexity class with respect to the polynomial-time hierarchy. Both clique-colouring and perfect graphs have attracted much attention due to a conjecture, posed by Duffus et al. in 1991, that perfect graphs are k-clique-colourable for some constant k, answered negatively by Charbit et al. in 2016. My co-authors are two former PhD students: one did his thesis on the complexity of edge and total coloring problems in 2010, and then co-supervised the thesis of the other one on the complexity of clique and biclique coloring problems in 2013.
This paper solves a problem left open in the PhD thesis of Maria Chudnovsky from Princeton University in 2003: the computational complexity of the Berge trigraph recognition. Maria kindly received me as visiting professor at Princeton in 2016 and generously introduced me to Sophie Spirkl, at a time a PhD student co-supervised by Paul Seymour and herself. I proposed to them a research problem that lies in the intersection of our research interests: the imperfect graph sandwich problem, which is equivalent to Berge trigraph recognition. To prove that the target problem can be solved in polynomial time, we introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We study the complexity of several graph decompositions related to perfect graphs, with respect to the graph sandwich problem, and the related partitioned and unpartitioned probe problems, resulting in polynomial-time algorithms or NP-hardness results.
Parameterized complexity is a recent branch of computational complexity that provides a framework for refined analysis of hard algorithmic problems. The strict terminal connection is a network design problem whose goal is to decide whether, given a graph and a set of vertices, there exits a tree subgragh having the set as its leaves. Network design problems are combinatorial questions of great practical and theoretical interest. Such problems are challenging tasks closely related to real-world applications. In this paper, we investigate the parameterized complexity of the strict terminal connection problem with respect to multiple parameters of the input. We establish a Polynomial versus NP-complete dichotomy with respect to the number of linkers in the tree and the maximum degree of the graph. We prove that the problem parameterized by the number of routers is hard and provide a kernelization when parameterized by the number of linkers. My co-authors are a current PhD student and an expert on this new area who is co-supervising the thesis.
The graph tessellation cover is motivated by its application to quantum walk models, where the evolution operator of the staggered model is obtained from a graph tessellation cover. We investigate the tessellation cover number for extremal graph classes, which are fundamental for the development of quantum walks in the staggered model. These results help to understand the complexity of the unitary operators necessary to express the evolution of staggered quantum walks. We establish tight upper bounds for the tessellation cover number related to chromatic parameters, which gives a complexity dichotomy between edge colorability and tessellability. The paper was published by Theoretical Computer Science Section C, Natural Computing, created in 2004 for research that explores the relationship between nature and computation. Among the co-authors there are three former PhD students: two of them did their theses on quantum computing in 2006 and 2020; the third one did his thesis on genome rearrangements in 2017 and contributed his expertise on computational complexity.