Universidade Federal do Ceará
ParGO – Paralelismo, Grafos e Otimização

Seminars

To access the history of seminars, since 2008, go here. Up to 2023, only the Portuguese version is available.

Upcoming seminars

Seminars happen every two weeks, on Fridays, at 1 pm.

2023

• Date and time: 01/11/2023 at 1pm (Wednesday).
• Place: Meeting room, Building 910.
• Speaker: Arnaud Knippel (INSA Rouen Normandie)
• Title: On bivalent and trivalent eigenvectors of the graph Laplacian.
• Abstract:  Given a simple non directed graph, the graph Laplacian can be defined as the difference between the diagonal matrix of the vertices degrees and the adjacency matrix. It’s a discrete version of the Laplacian operator in the wave equation and appears in many applications where there are dynamical flows with a conservation law.
  In some models from theoretical physics, the study of  a nonlinear graph wave equation the the possibility to extend normal modes into nonlinear periodic orbits leads is related to graphs affording eigenvectors with only the values 1, 0 or -1.
  We call these graphs bivalent graphs if they afford bivalent eigenvectors (with values 1 and -1 ) and trivalent graphs if they afford trivalent eigenvectors. In the case of the so-called phi4 model, the related graphs are exactly the bivalent and trivalent graphs, and we caracterize all of them. More precisely, the bivalent graphs are the regular bipartite graphs and their extensions by adding edges between two equal-valued vertices. The trivalent graphs are obtained from the soft regular graphs (all the non zero vertices have the same degree) by applying some transformations. This is a joint work with Jean-Guy Caputo and Imene Khames.

• Date and time: 20/10/2023 at 1pm.
• Place: Meeting room, Building 910.
• Speaker: Ana Shirley Silva (ParGO).
• Title: On Computing Optimal Temporal Branchings.
• Abstract: A temporal graph is a graph whose edges are available only at prescribed times. It can model many practical situations, like proximity networks, public transportation and bitcoin transactions. In this context, different notions of optimality of paths arise. In this talk, we will explore the problem of computing paths starting at a given node (called branching) that achieve each of these criteria. We give polynomial time algorithms for most of the criteria, except for the fastest, which we prove to be NP-hard. This is a joint work with Daniela Bubboloni, Costanza Catalano and Andrea Marino. It was presented at FCT 2023, in Trier, Germany.

• Date and time: 06/10/2023 at 1pm.
• Place: Room 3 of Building 914, Campus do Pici.
• Speaker: Michael Souza (Statistics Department)
• Title: From scarcity to abundance?
• Abstract: In this scientific dissemination lecture, the emerging potential of ChatGPT as an innovative tool for advances in education will be discussed. Recent advances in the area of natural language processing will also be discussed.

• Date and time: 29/09/2023 at 1pm.
• Place: Room 3 of Building 914 (Math Department)
• Speaker: Allen Ibiapina.
• Title: Snapshot disjoint paths in temporal graphs.
• Abstract: A temporal graph with lifetime τ is a pair (G,L) where L is a label function on the edges of G that tells us in which timesteps in [τ ] each edge is going to be active. It can model for instance the moments at which direct communication between nodes of a network was established throughout a time window. Many other practical situations can be modeled in a temporal graph, from proximity networks, to public transportation and bitcoin transactions. In this talk, we will introduce a new kind of robustness on these graphs and present computational complexity results of related problems. This is a joint work with Ana Shirley Silva and has received the Best Student Paper Award at SAND 2023 (Pisa, Italy).

• Date and time: 13/09/2023 at 1pm.
• Place: Seminar room of Building 952.
• Speaker: Pedro Paulo de Medeiros (PhD student supervised by Prof. Júlio Araújo)
• Title: On the hull and interval numbers of oriented graphs.
• Abstract: In this work, for a given oriented graph $D$, we study its interval and hull numbers, denoted by $\oin(D)$ and $\ohn(D)$, respectively, in the oriented geodetic, $\opc$ and $\opsc$ convexities. This last one, we believe to be formally defined and first studied in this paper, although its undirected version is well-known in the literature. Concerning bounds, for a strongly oriented graph $D$ and the oriented geodetic convexity, we prove that $\ohng(D)\leq m(D)-n(D)+2$ and that there is at least one such that $\ohng(D) = m(D)-n(D)$. We also determine exact values for the hull numbers in these three convexities for tournaments, which imply polynomial-time algorithms to compute them. These results allow us to deduce polynomial-time algorithms to compute $\ohnp(D)$ when the underlying graph of $D$ is split or cobipartite. Moreover, we provide a meta-theorem by proving that if deciding whether $\oing(D)\leq k$ or $\ohng(D)\leq k$ is \NP-hard or \W[i]-hard parameterized by $k$, for some $i\in\mathbb{Z_+^*}$, then the same holds even if the underlying graph of $D$ is bipartite. Next, we prove that deciding whether $\ohnp(D)\leq k$ or $\ohnps(D)\leq k$ is $\W[2]$-hard parameterized by $k$, even if the underlying graph of $D$ is bipartite; that deciding whether $\oinp(D)\leq k$ or $\oinps(D)\leq k$ is $\NP$-complete, and the same for $\ohnps(D)\leq k$ even if $D$ has no directed cycles and the underlying graph of $D$ is a chordal bipartite graph; and that deciding whether $\oinp(D)\leq k$, and the same for $\oinps(D)\leq k$ is $\W[2]$-hard parameterized by $k$, even if the underlying graph of $D$ is split. Finally, also argue that the interval and hull numbers in the $\opc$ and $\opsc$ convexities can be computed in polynomial time for graphs of bounded tree-width by using Courcelle’s Theorem.

• Date and time: 01/09/2023 at 1pm.
• Place: Room 2 of Building 952.
• Speaker: Claro Henrique Silva Sales (Msc. student supervised by Prof. Heron, MDCC).
• Title: TBA.
• Abstract: TBA.

• Date and time: 18/08/2023 at 1pm.
• Place: Room 3 of building 914.
• Speaker: Andrea Marino (Universitá degli Studi di Firenze).
• Title: Optimal Paths in Temporal Graphs.
• Abstract: Graphs are everywhere and successfully model data, effectively representing millions or billions of connections: the complexity of the involved entities is enclosed in the vertices of the graphs and the complex mechanisms of interaction among them are described by an arc. However, connections between the involved entities are often dynamic, i.e. they occur at specific times. For instance, in a public transportation network, one wishes to know not only which stops are connected by bus lines, but also at what time such buses pass by each stop. This type of situation led the scientific community to define temporal graphs, that is, graphs in which edges can appear and disappear over time. In this kind of graphs, paths make sense only if they respect the flow of time, as each leg of a trip must be temporally consistent with the previous one. In this scenario, the traditional notion of shortest path in static graphs can translate into several possible optimization criteria in the case of temporal graphs, namely earliest arrival path, latest departure path, minimum duration (called fastest paths), minimum travel time (called shortest paths). In this talk we will see how to compute such paths in an efficient way.

• Date and time: 29/06/2023 at 1pm.
• Place: Room 3 of Building 914 (Mathematics Department).
• Spearker: Carla Negri Lintzmayer (UFABC).
• Title: A tour of approximation algorithms for the TSP Problem (and some of their uses).
• Abstract: In this seminar I will give a brief introduction to approximation algorithms and also present some latest results of problems I’ve been working on.
  These two parts of the lecture rely heavily on the famous Traveling Salesman Problem (TSP).

• Date and time: 26/06/2023 at 8am.
• Place: Meetings room of Building 952.
• Spearker: Allen Ibiapina (PhD defense, advised by Ana Shirley F. Silva).
• Title: Menger’s Theorem and Related Problems on Temporal Graphs.
• Abstract: Temporal graphs are an important tool for modeling time-varying relationships in dynamic systems. Among the problems of interest, paths and connectivity problems have been the ones that have attracted the most attention of the community. The famous Menger’s Theorem says that, for every pair of non-adjacent vertices s, z in a graph G, the maximum number of internally vertex disjoint s, z-paths in G is equal to the minimum number of vertices in G\ {s, z} whose removal destroys all s, z-paths (called and s, z-cut). This combined with flow techniques also leads to polynomial time algorithms to compute disjoint paths and cuts. A natural question is therefore whether such results carry over to temporal graphs, where the paths/walks between a pair of vertices must respect the flow of time. In this thesis, we investigate three possible types of robustness, each of which leads to the definition of two optimization parameters, one concerning the maximum number of disjoint paths, and the other the minimum size of a cut. We give theoretical results about the validity of Menger’s Theorem and computational complexity results for the decision problems related to each parameter.

• Date and time: 23/06/2023 at 1pm.
• Place: Room 3 of Building 914 (Math Department).
• Speaker: Walner Mendonça.
• Title: Ramsey-goodness in dense graphs.
• Abstract: We say that a graph $G$ is Ramsey to the pair of graphs \((F,H)\), if
  in every colouring of the edges of $G$ with the colours red and blue,
  there is a red copy of $F$ or a blue copy of $H$. Chvátal showed that
  the complete graph $K_n$ is Ramsey for the pair $(K_r,P_t)$, as long
  as $n \geq (r-1)(t-1) + 1$. In this seminar, we will generalize
  Chvátal’s theorem by showing that for any graph $G$ with $n
  =(r-1)(t-1) + 1$ vertices and $\delta(G)\geq n – t/2$, we have that
  $G$ is Ramsey for $(K_r,P_t)$. With this result, we initiate the study
  of Ramsey-goodness in dense graphs.

• Date and time: 16/06/2023 at 9am.
• Place: Online:
• Speaker: Emanuel Castelo (Msc. defense, advised by Rafael Castro de Andrade).
• Title: Contributions to the k-color shortest path problem.
• Abstract: Given a digraph D = (V, A), where for all arcs (i, j) in A we have an associated positive real cost d_{ij} and a color c(i, j), a positive integer k, a source s, and a destination t, the k-Color Shortest Path Problem consists in finding the shortest (s, t)-path in D while using at most k distinct colors. We propose valid inequalities for the problem that proved to strengthen the linear relaxation of an existing Integer Linear Programming formulation. An exponential set of valid inequalities defines a new formulation for the problem and is solved by using a branch-and-cut algorithm. We introduce more challenging instances of the problem and present numerical experiments for both benchmark and the new instances. Finally, we evaluate the individual and the collective use of the valid inequalities. Computational results for the proposed ideas and for existing solution approaches for the problem showed the effectiveness of the new inequalities in handling the new instances both in terms of execution times and improving their linear relaxed solutions.

• Date and time: 02/06/2023 at 1pm.
• Place: Room 3 of Building 914 (Mathematics Department).
• Speaker: Alexandre Cezar (Phd Student – PGMAT).
• Title: On (acyclic) proper orientations and the cartesian product.
• Abstract: Given an orientation $D$ of the edges of a simple graph $G$, the indegree of a vertex $v \in V(G)$, $d_D^{-}(v)$, is the number of arcs with head in $v$. Such orientation induces a coloring $\phi(v) = d_D^{-}(v)+1$ of $G$. We say that $D$ is a proper $k$-orientation if $\phi$ is a proper $(k+1)$-coloring of $G$. The proper orientation number of $G$, denoted by $\po(G)$, is the least positive integer $k$ such that $G$ admits a proper $k$-orientation.
  We study a variation of this problem where we consider the orientation $D$ to be acyclic. To the best of our knowledge this is the first article considering this variation. Furthermore, we also study the parameter $\po$ for graphs obtained by the cartesian product of graphs, introducing the concept of chaotic set of proper orientations, that is a set where in different orientations, the same vertex has different indegrees.

• Date and time: 25/05/2023 at 1pm.
• Place: Meetings room of Building 952.
• Speaker: Jonas Costa Ferreira da Silva (PhD defense).
• Title: Structural and Complexity Studies in Inversions and Colouring Heuristics of (Oriented) Graphs.
• Abstract: This thesis is divided in two parts, where the first one concerns the inversion number of oriented graphs. Let D be an oriented graph. The inversion of a set X of vertices in D reverses the direction of all arcs with both extremities in X.  The inversion number of D, denoted by inv(D), is the minimum number of inversions needed to make D acyclic. We study some bounds and properties of the inversion number and the complexity of computing this parameter.
  The second part of this work is about b-greedy colourings and z-colourings which are heuristics obtained by the combination of both greedy and b-colourings. The b-Grundy number(resp. z-number) of a graph G is the largest integer k such that G admits a b-greedy colouring (resp. z-colouring), that is, the worst case of this heuristic for G. We prove that it is NP-hard to obtain each of these parameters and study its behaviour in some classes of graphs.

• Date and time: 24/05/2023 at 1pm.
• Place: Meetings room of Building 952.
• Speaker: Prof. Celina Figueiredo (UFRJ).
• Title: A Perfect from Computational Biology to Quantum Computing.
• Abstract: I’ll revisit my contributions to the P versus NP millennium problem and the computational complexity of combinatorial problems, especially those arising in Computational Biology and Quantum Computing, through 20 PhD theses, mine and of my students. I’ll explain how the dichotomy NP-complete versus polynomial-time of long-standing problems together with their multivariate analysis is settled. Yet, intriguing questions remain.

• Date and time: 12/05/2023 at 1pm.
• Place: Meetings room of Building 952.
• Speaker: Prof. Victor Campos.
• Title: AWESome Paths and applications to half-integral linkages
• Abstract:We present new min-max relations in digraphs between the number of paths satisfying certain
  conditions and the order of the corresponding cuts. We define these objects in order to capture, in
  the context of solving the half-integral linkage problem, the essential properties needed for reaching
  a large bramble of congestion two (or any other constant) from the terminal set. This strategy has
  been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to
  abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max
  relations, one consisting in applying Menger’s Theorem on appropriately defined auxiliary digraphs,
  and an alternative simpler one using matroids, however with worse polynomial running time.As an application, we manage to simplify and improve several results of Edwards et al. [ESA
  2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs.
  Concerning the former, besides being simpler, our proof provides an almost optimal bound on the
  strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large
  bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard
  case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical
  grids, hence yielding much better bounds and being somehow independent of a particular topology.
  We hope that our min-max relations will find further applications as, in our opinion, they are
  simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.This is a joint work with Jonas Costa, Raul Lopes and Ignasi Sau.

• Date and time: 28/04/2023 at 13hs.
• Place: Meetings room of Building 910.
• Speaker: Prof. Rudini Sampaio (ParGO Group).
• Title: Identifying Codes in Hexagonal Grids.
• Abstract: for the abstract, go here.

• Date and time: 14/04/2023 at 13hs.
• Place: Meetings room, Building 910 (Statistics Dep. and Computer Science Dep.)
• Open problems session.

• Date and time: 31/03/2023 at 13hs.
• Place: Room 3 of building 914.
• Speaker: Pierre Aboulker (TALGO – École Normale Supérieure de Paris).
• Title: Induced subdigraphs of digraphs with large dichromatic number (presentation in english).
• Abstract:The dichromatic number of a directed graph is the smallest number of colours needed to colour the vertices in such a way that no directed cycle is monochromatic. We will give a short introduction to this notion to show that it generalises the  chromatic number of undirected graphs. We will then investigate what induced subdigraphs must appear in all digraphs with sufficiently large dichromatic number.

• Date and time: 22/03/2023 at 13hs (Wednesday).
• Place: Room 3 of building 914.
• Speaker: Raul Lopes (TALGO – École Normale Supérieure de Paris).
• Title: Twin-width VIII: delineation and win-wins (presentation in english).
• Abstract: Cographs are exactly the graphs that can be contracted into a single vertex by iteratively contracting twins. Informally, the twin-width of an undirected graph G can be seen as an approximation of how tightly G can be approximated by a cograph. As an application, Bonnét et al. [Journal of the ACM, 2021] showed that FO model checking is FPT parameterized by the size of the formula in graphs of bounded twin-width, provided that a contraction sequence is given.
  In this talk, we formally present the notion of twin-width, with some examples and applications. We discuss some of the difficulties associated with obtaining an FPT approximation algorithm that either shows that G has twin-width at most k or finds a certificate that G has twin-width at least f(k). We present the concept of delineated classes, introduced by Bonnét et al. [IPEC, 2022], as an alternative to the missing algorithm.

• Date and time: 17/03/2023 at 13hs.
• Place:Room 3 of building 914.
• Open problems session.