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

Seminars

To access the history of seminars, since 2008, go here.

Upcoming seminars

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

2025

• Date and time: 21/02/2025 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Carlos Miguel Moreira Gonçalves (UFC).
• Title: OTIMIZAÇÃO DE REQUISIÇÕES NO GOOGLE MAPS API
• Abstract: Compreender e otimizar a mobilidade urbana depende fortemente de estudos de tráfego. Uma ferramenta chave nesses estudos é o grafo da cidade juntamente com a matriz Origem-Destino (OD). A matriz OD quantifica a demanda de viagens ao mostrar o número de pessoas que se deslocam de cada nó de origem para cada nó de destino dentro de um período de tempo específico. Combinar esta matriz com algoritmos de otimização permite calcular o fluxo de tráfego em cada via (rua, avenida, …) e auxiliar na tomada de decisões de planejamento urbano e gestão de tráfego.Estimar matrizes OD para cidades inteiras é desafiador devido ao alto custo de aquisição de dados. Métodos tradicionais, como extensas pesquisas de viagens e entrevistas, são caros e demorados. Para lidar com isso, propomos uma abordagem alternativa: inferir a matriz OD a partir de tempos de viagem observados. Esses tempos de viagem podem ser obtidos de APIs de mapeamento e navegação como Google Maps e Mapbox, que fornecem cálculos de rotas e estimativas de tempo. Essas APIs permitem solicitações de rotas entre uma origem e um destino, incluindo até 24 paradas intermediárias em uma única solicitação.Como cada solicitação de API tem um custo fixo independentemente do número de paradas intermediárias, o problema central abordado neste trabalho é minimizar o número de solicitações necessárias para obter os tempos de viagem para todas as arestas do grafo da cidade. Essa otimização possibilitará uma coleta de dados mais extensa e facilitará o estudo de várias cidades.

• Date and time: 14/02/2025 às 13hs.
• Place: Sala de seminários do bloco 952.
• Speaker: Prof. Wladimir Araujo (UFC).
• Title: Problema da Máxima Interseção de k-Subconjuntos (kMIS)
• Abstract: Quando precisamos escolher indivíduos em um grupo, muitas vezes buscamos aqueles que têm mais características em comum. Esse tipo de desafio deu origem a uma série de problemas de otimização, onde o objetivo é maximizar as conexões entre dois grupos diferentes — como indivíduos e suas características —, sem nos aprofundarmos tanto nas relações internas de cada um desses grupos.Dentro dessa família de problemas, um dos mais interessantes é o Problema da Máxima Interseção de k-Subconjuntos (kMIS). Imagine que temos um conjunto 𝐵, que pode ser uma lista de características, e uma coleção de subconjuntos de 𝐵, onde cada subconjunto pode representa um indivíduo. A ideia é simples: escolher exatamente 𝑘 desses subconjuntos de forma que a interseção entre eles — ou seja, as características que todos compartilham — seja a maior possível. Em outras palavras, queremos encontrar um grupo de 𝑘 indivíduos que tenham o máximo de coisas em comum.Esse problema possui aplicações bem práticas em áreas importantes. Por exemplo, na privacidade de dados, ele pode ser usado para divulgar informações de forma que o anonimato seja preservado. Nas redes sociais, ele pode ser aplicado para recomendar conexões ou conteúdos com base em interesses comuns.Nesta apresentação, vamos explorar as principais ferramentas e técnicas que foram criadas para resolver o kMIS.

• Date and time: 31/01/2025 às 13hs.
• Place: Sala de seminários do bloco 952.
• Speaker: Prof. Júlio Araújo  (UFC).
• Title: On the parameterized complexity of computing good edge-labelings
• Abstract:

• Date and time: 17/01/2025 às 13hs.
• Place: Sala de seminários do bloco 952.
• Speaker: Prof. Heron Carvalho  (UFC).
• Title: CloudClusters.jl, Um Pacote para Computação Multicluster Baseada em Nuvens usando a linguagem Julia
• Abstract:  Provedores de serviços IaaS tem se constituído como uma alternativa de fato para aplicações de Computação de Alto Desempenho (HPC), oferecendo um catálogo diversificado de tipos de instâncias de máquinas virtuais com processadores e aceleradores de última geração, possivelmente conectados por meio de interconexões de baixa latência e alta largura de banda. Isso possibilita a criação de plataformas de computação em cluster baseadas em infraestrutura de nuvem que rivalizam com alternativas on-premises. Apresentamos uma contribuição de nossa pesquisa para a comunidade Julia, o pacote CloudClusters.jl, que usa uma abordagem de infraestrutura como código (IaC) para construir sistemas de computação paralela em programas Julia.

2024

• Date and time: 18/12/2024 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Prof. Fabio Chalub (NOVA, Portugal).
• Title: Group centrality in optimal and suboptimal vaccination for epidemic models in contact networks.
• Abstract:  The pursuit of strategies that minimize the number of individuals needing vaccination to control an outbreak is a well-established area of study in mathematical epidemiology. However, when vaccines are in short supply, public policy tends to prioritize immunizing vulnerable individuals over epidemic control. As a result, optimal vaccination strategies may not always be practical for informing real-world public policies. In this work, we focus on a disease that results in long-term immunity and spreads through a heterogeneous population, represented by a contact network. We study four well-known group centrality measures and show that the GED-Walk offers a reliable means of estimating the impact of vaccinating specific groups of individuals, even in suboptimal cases. Additionally, we depart from the search for target individuals to be vaccinated and provide proxies for identifying optimal groups for vaccination. While the GED-Walk is the most useful centrality measure for suboptimal cases, the betweenness (a related, but different centrality measure) stands out when looking for optimal groups. This indicates that optimal vaccination is not concerned with breaking the largest number of transmission routes, but interrupting geodesic ones.
  This is a joint work with Jorge O. Cerdeira and Matheus Hansen (NOVA Math, Universidade NOVA de Lisboa, Portugal)

• Date and time: 29/11/2024 às 14hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Geovane Cavalcante (UFC).
• Title: Modelos Matemáticos sob a Perspectiva da Teoria Espectral de Grafos para o Balanceamento de Carga em Redes de Transmissão de Energia
• Abstract: A crescente demanda por energia elétrica torna essencial o projeto e a manutenção de redes elétricas confiáveis, a fim de evitar falhas como blecautes, os quais podem gerar grandes prejuízos à sociedade. Este estudo concentra-se na identificação de linhas críticas de transmissão, analisando a potência elétrica em cada uma delas, para assegurar a confiabilidade da rede e prevenir apagões. Adotamos uma abordagem geométrica baseada na teoria espectral de grafos, desenvolvendo formulações para o problema de balanceamento de carga e propondo uma solução fundamentada nas condições de otimalidade da função quadrática, o que resulta em um processo mais rápido e eficiente.

• Date and time: 22/11/2024 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Rômulo da Silva Marques (Unicamp).
• Title: A Probabilistic Approach in the Search Space of the Molecular Distance Geometry Problem
• Abstract: Proteínas são moléculas orgânicas essenciais aos processos biológicos e suas funções estão diretamente atreladas aos seus formatos tridimensionais. Matematicamente, o problema de determinar a estrutura 3D de moléculas de proteínas pode ser modelado como um Discretizable Molecular Distance Geometry Problem (DMDGP). O termo “Discretizável” deve-se ao seguinte fato: em um DMDGP, o espaço de soluções pode ser organizado em uma árvore binária, o que implica que este problema pode ser resolvido de maneira exata e discreta. O método discreto estado-da-arte que resolve um DMDGP é chamado de Symmetry-Based Build-Up (SBBU), e emprega fortemente as propriedades de simetria presentes na árvore binária associada a um DMDGP. Em uma etapa inicial, o SBBU explora trechos da árvore binária do DMDGP por meio de uma Busca em Profundidade (Depth First Search – DFS). Nota-se, contudo, que tal abordagem de exploração da árvore de busca faz pouco uso dos dados de estruturas de proteínas disponíveis publicamente. O presente trabalho analisa todas as instâncias oriundas de experimentos de Ressonância Magnética Nuclear presentes no Protein Data Bank (PDB) (uma amostra de 14.382 moléculas) e verifica que a distribuição das soluções dos DMDGPs de proteínas é muito diferente da distribuição uniforme, indicando que a Natureza “prefere” alguns padrões em detrimento de outros. Desenvolvemos uma versão do algoritmo SBBU que, ao invés de explorar o espaço de soluções do DMDGP usando a busca em profundidade (DFS), navegará pela árvore binária dando preferência aos padrões de soluções mais prováveis (Frequency-Based Search – FBS).

• Date and time: 08/11/2024 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Prof. Ignasi Sau (Université de Montpellier).
• Title: On the existence of polynomial kernels for structural parameterizations of hitting problems
• Abstract: When dealing with a parameterized problem, one of the main questions is to determine whether it admits a polynomial kernel, that is, a polynomial-time algorithm that reduces an instance to an equivalent one with size polynomially bounded as a function of the parameter. Of particular interest are the so-called “structural parameterizations”, which consider parameters that can typically be arbitrarily smaller than the solution size. Hence, providing a polynomial kernel for such a parameter is a stronger result than one for the solution size. In this talk I will survey some recent results about the existence of polynomial kernels for structural parameterizations of Vertex Cover, as well as its generalizations consisting in hitting some fixed graph as a minor or as an (induced) subgraph. If time permits, I will show some of the techniques that are used to obtain positive and negative results in this area.
  Based on joint work with Marin Bougeret and Bart M. P. Jansen.

• Date and time: 01/11/2024 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Prof. Uérverton Souza (IMPA).
• Title: Induced Tree Covering and the Generalized Yutsis Property
• Abstract: The Yutsis property of a simple, connected, and undirected graph is the property of partitioning its vertex set into two induced trees. Although the first impression is that such a property is quite particular, its studies emerge from the quantum theory and such a property is more general than Hamiltonicity on planar graphs since a planar graph satisfies the Yutsis property if and only if its dual is Hamiltonian. Despite the fact that recognizing Yutsis graphs is NP-complete even on planar graphs, it is still possible to consider two even more challenging problems:
  (i) the recognition of k-Yutsis graphs, which are graphs that have their vertex sets partitioned into k induced trees, for a fixed k> 2;
  (ii) to find the minimum number of vertex-disjoint induced trees that cover all vertices of a graph G, which is called the tree cover number of G.
  In this talk, we present some results regarding the (parameterized) complexity of the tree cover number computation and k-Yutsis graph recognition.

• Date and time: 30/08/2024 às 13hs.
• Place: Sala de seminários do bloco 952.
• Speaker: Prof. Rudini Sampaio  (UFC).
• Title: Jogos de Convexidade em Grafos
• Abstract:  O primeiro artigo de convexidade em grafos gerais, em inglês, é o artigo “Convexity in graphs”, publicado em 1981. Um de seus autores, Frank Harary, introduziu em 1984 os primeiros jogos de convexidade de grafos, focados na convexidade geodésica, que são jogos imparciais e foram investigados em uma sequência de cinco artigos até 2003. Somente em 2023, provou-se o primeiro resultado de complexidade PSPACE em jogos imparciais de convexidade e obteve-se algoritmo polinomial para árvores a partir da Teoria de Sprague-Grundy. Neste artigo, introduzimos as variantes partizan desses jogos imparciais na convexidade geodésica e as estendemos para outras convexidades de grafos, obtendo estratégias vencedoras e resultados de complexidade. Obtemos estratégias vencedoras para geometrias convexas gerais e estratégias vencedoras para árvores a partir da teoria combinatória dos jogos de Conway em jogos partizan. Provamos também que o jogo normal e o jogo misère do jogo partizan da envoltória na convexidade geodésica é PSPACE-completo mesmo em grafos com diâmetro dois. Esse é um trabalho em coautoria com Samuel Araújo, João Marcos Brito, Raquel Foz e Rosiane de Freitas.

• Date and time: 23/08/2024 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Prof. Andrea Marino  (Università degli Studi di Firenze).
• Title: On Computing Large Temporal (Unilateral) Connected Components
• Abstract:  A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, $\tau$. Paths are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasing (i.e., non-decreasing), depending on the scenario. The classical concept of connected components and also of unilateral connected components in static graphs naturally translate to temporal graphs in several non-equivalent ways.
  In this talk, we address the following fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size $k$, parameterized by $\tau$, by $k$, and by $k+\tau$? We show that this question has a different answer depending on the considered definition of component and whether the temporal graph is directed or undirected. (ii) What is the minimum running time required to check whether a subset of vertices are pairwise reachable? A quadratic-time algorithm is known but, contrarily to the static case, a better running time is unlikely unless SETH fails. (iii) Is it possible to verify whether a subset of vertices is a component in polynomial time? We show that depending on the definition of temporal component this test is NP-complete.

• Date and time: 09/08/2024 às 13hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Joab da Silva Rocha (UFC).
• Title: HEURÍSTICAS PARA O FLOORPLANNING DE CIRCUITOS VLSI
• Abstract:  O problema de floorplanning em circuitos VLSI (Very Large Scale Integration) envolve a disposição eficiente dos blocos funcionais em um chip, de forma a otimizar critérios como área total, dissipação de potência e comprimento das conexões. Este trabalho apresenta o desenvolvimento de novas heurísticas para abordar esse problema, focando no agrupamento dos componentes do circuito com base na força de conexão entre eles. Nossa abordagem utiliza o conceito de “dividir para conquistar”, onde o circuito é dividido em grupos menores que são otimizados individualmente.

• Date and time: 12/04/2024 às 13hs.
• Place: Sala de seminários do Bloco 952.
• Speaker: Alex Talon (UFC).
• Title: Conjuntos dominantes em grid graphs: minimizar e contar.
• Abstract:  A dominating set in a graph is a set of vertices such that each vertex not is this set has a neighbor in this set. Finding the size of a minimum dominating set in grid graphs has been proved by Gonçalves et al. to be constant time solvable. We proved the same for variants of this problem (2 domination, Roman domination). We also counted the dominating, minimal dominating (and their total domination variant) in grids. All this work involves the use of a computer program I made.

• Date and time: 15/03/2024 às 16hs.
• Place: Sala de reuniões do Bloco 910.
• Speaker: Carlos Hoppen (UFRGS).
• Title: Generalizações do Problema de Erdős-Rothschild: Resultados e Problemas em Aberto.
• Abstract:  Nos últimos anos, houve uma série de avanços em variantes de um problema extremal sobre colorações de arestas que foi proposto, na década de 70, por Erdős e Rothschild. O objetivo dessa palestra é enunciar esse problema, descrever os principais resultados já obtidos e técnicas utilizadas, e apresentar diversos problemas em aberto.

• Date and time: 08/03/2024 às 13hs.
• Place: Sala de seminários do Bloco 952.
• Speaker: Cláudia Linhares Sales (UFC).
• Title: Obstáculos à carreira para as mulheres das áreas de STEM (Ciência, Tecnologia, Engenharia e Matemática).
• Abstract:  O dia 8 de março, dia internacional da mulher, criado pela demanda de trabalhadoras e trabalhadores, é fundamentalmente um dia de ativismo político em prol da igualdade de direitos entre os gêneros.  Como na prática, as sociedades em geral, inclusive de países mais ricos, estão ainda longe desse ideal, torna-se fundamental a comemoração desse dia para reflexão de toda a sociedade sobre um problema que nos prejudica a todos, que é a cultura que deprecia o trabalho e a capacidade da mulher, a cultura da posse sobre as mentes e corpos femininos, a cultura do assédio moral e sexual, a cultura da violência para resolução de conflitos com mulheres e a cultura que promove a mulher como ser inferior na escala social, única responsável pelo trabalhos domésticos e cuidados da família. Nesse seminário, por ocasião da data, vamos refletir sobre quais empecilhos afastam as mulheres na carreira nas áreas de Ciência, Tecnologia, Engenharia e Matemática e os enormes prejuízos que isso traz para a sociedade.

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.