Detailed Program – ForWorC II
- 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)
Abstract: A path separates an edge e from an edge f if it contains the former and not the latter. How many paths do we need to separate any edge from any other? This question was first asked by Katona in 2013, in line with the general study of separating systems initiated by Rényi in 1961. In this talk, we show that the answer is linear in the number of vertices, thus confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. We focus on the proof method and possible extensions. This is based on joint work with Bonamy, Dross, Naia and Skokan.
- 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.
- Plenary Session: Rosiane de Freitas (IComp/UFAM, Brazil)
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.
- Plenary Session: Tatiane Figueiredo (UFC, Brazil)
Title: Application of Integer Linear Programming techniques to solve team formation problems in social networks
Abstract: In the face of hard competition and technological challenges, an increasing number of companies has used group work strategies as an effective approach to resolving employee motivation issues and accomplishing organizational productivity goals. For several decades, the OR literature has dedicated different studies to the problem of forming worker teams. In this lecture, we will study Integer Linear Programming models and techniques to solve for the Team Formation Problem using data from social networks.
- Plenary Session: Carlos Hoppen (UFRGS, Brazil)
Title: Gaussian Elimination using a tree decomposition
Abstract: Every matrix $mxn$ $A=(a_{ij})$ with elements on a field can be associated with an underlying bipartite graph $G=(V,E)$ with vertex set $V=\{v_1,\ldots,v_m\}\cup\{w_
- Plenary Session: Nicolas Nisse (INRIA Sophia Antipolis, Université Côte d’Azur, France)
Abstract: A (di)graph $H$ has the Erd\H{o}s-P\’osa (EP) property for (butterfly) minors if there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ such that, for any $k\in \mathbb{N}$ and any (di)graph $G$, either $G$ contains at least $k$ pairwise vertex-disjoint copies of $H$ as (butterfly) minor, or there exists a subset $T$ of at most $f(k)$ vertices such that $H$ is not a (butterfly) minor of $G-T$. It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case where a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In this work, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly $3$-connected strong digraph has the EP property. This is a joint work with J. Bensmail, V. Campos, A-K. Maia and A. Silva.
- Plenary Session: Mario Valencia (Université de Lorraine, France)
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)
- Plenary Session: Ignasi Sau (LIRMM, CNRS, France)
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.
- Mini-course: Roberto Parente (UFBA, Brazil) and Guilherme Mota (USP, Brazil)
- Mini-course: Ignasi Sau (LIRMM, CNRS, France)
