Universidade Federal do Ceará
Pós-graduação em Matemática

• Plenary Session: Júlio Araújo (UFC, Brazil)

Title: On graph convexity parameters in oriented graphs

Abstract: In this talk, we survey results on graph convexity parameters in oriented graphs, which special focus on Computational Complexity results. In particular, we will present hardness results for the hull and interval numbers in the geodesic, P3 and P3* convexities in oriented graphs D whose underlying graph is bipartite, or cobipartite, or split, or when D is acyclic or even a tournament in some cases. We also present polynomial time algorithms for cacti, graphs of bounded treewidth, and tournaments in some other cases. We also show avenues for further research. These results were obtained in distinct collaborations with P. Arraes, A. K. Maia, T. Marcilon, P. P. Medeiros and L. Penso.

• Plenary Session: Fábio Botler (UFRJ, Brazil)

• Plenary Session: Érika Coelho (UFG, Brazil)

Title: Locating-dominating set in graphs
Abstract: A locating dominating set is a dominating set D that locates all the vertices in the sense that every vertex not in D is uniquely determined by its neighborhood in D. In this work some results related to this variation of the dominating problem will be presented.

Title: Complexity aspects in graphs and algorithms for special path optimization problems with temporal constraints

Abstract: In this research, path problems in graphs involving temporal constraints are investigated. In particular, two large classes of classical problems are being addressed: shortest path problems with time-interval constraints; and, vehicle routing problems with scheduling constraints. The objective is to analyze mathematical-computational aspects related to the incorporation of dynamic characteristics of current urban logistics, where theoretical aspects of modeling and algorithmic resolution that best characterize problems with special time constraints are explored, dealing with general NP-complete problems and polynomial cases into special classes of graphs. Path and route re-optimization strategies, as well as dynamic programming algorithms, are proposed.

Title: The rotation distance and diameter of graph associahedra
Abstract: The associahedron A(G) of a graph G has the property that its vertices can be thought of as the search trees on G and its edges as the rotations between two search trees. If G is a simple path, then A(G) is the usual associahedron and the search trees on G are binary search trees. In this work, we investigate the diameter of graph associahedra as a function of some graph parameters. We give a tight bound of Θ(m) on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. We also prove that the maximum diameter of associahedra of graphs of pathwidth two is Θ(nlogn). We also give the exact diameter of the associahedra of complete split and of unbalanced complete bipartite graphs.
Computing distances in the graph of A(G) (or equivalently, the rotation distance between two binary search trees) is a major open problem. Here, we consider the different case when G is a complete split graph. In that case, A(G) interpolates between the stellohedron and the permutohedron, and all the search trees on G are brooms. We show that the rotation distance between any two such brooms and therefore the distance between any two vertices in the graph of the associahedron of G can be computed in quasi-quadratic time in the number of vertices of G.
This is a joint work with Jean Cardinal (Université Libre de Bruxelles) et Lionel Pournin (Université Sorbonne Paris-Nord)

Title: Compound logics for modification problems

Abstract: We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth (hence, for which Courcelle’s theorem does not apply). Our main result is that, for this compound logic, model-checking can be done in quadratic time.

The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle’s theorem and Gaifman’s theorem. We finally prove extensions where the target property is expressible in FOL+DP, i.e., the enhancement of FOL with disjoint-paths predicates.

Joint work with Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos.

Abstract: A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. The theory of Graph Minors developed by Robertson and Seymour in a series of more than 20 papers (1983-2012) is one of the most impressive modern results in Graph Theory and Combinatorics. The goal of this theory was to prove Wagner’s conjecture (asserting that there is no infinite antichain with respect to the graph minor relation), but as a byproduct of the proof, a number of algorithmic applications have also emerged from it. In this course we will focus on the algorithmic aspects of graph minor theory, with special emphasis on the crucial notion of treewidth. To describe some of these algorithmic applications, we will use the modern framework of Parameterized Complexity developed in the 90’s by Downey and Fellows, and which has established itself as one of the most active areas of Algorithmic Graph Theory. In a nutshell, the main objective of Parameterized Complexity is to analyze the complexity of optimization problems in a more refined way than just the classic “P vs NP” dichotomy. For this, one measures the complexity of an algorithm not only in terms of its total input size, but also as a function of an additional parameter that can capture the inherent difficulty of the considered problem.