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

Seminários

2022   2021   2016 a 2020   2008 a 2015

Próximos

Os seminários estão ocorrendo de maneira presencial, sextas às 13hs, a cada duas semanas.

2023

• Data e horário: 01/11/2023 às 13hs (quarta).
• Local: Sala de reuniões, Bloco 910.
• Palestrante: Arnaud Knippel (INSA Rouen Normandie)
• Título: On bivalent and trivalent eigenvectors of the graph Laplacian (palestra proferida em inglês).
• Resumo:  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.

• Data e horário: 20/10/2023 às 13hs.
• Local: Sala de reuniões, Bloco 910.
• Palestrante: Ana Shirley Silva.
• Título: Calculando Ramificações Temporais Ótimas
• Resumo: Um grafo temporal é um grafo cujas arestas estão disponíveis apenas em momentos prescritos. Pode modelar muitas situações práticas, como redes de proximidade, transporte público e transações de bitcoin. Neste contexto, surgem diferentes noções de otimalidade de caminhos. Nesta palestra, iremos explora o problema de calcular caminhos começando em um determinado nó (chamado de ramificação) que atenda a cada um desses critérios. Fornecemos algoritmos polinomiais para a maioria dos critérios, exceto para caminhos mais rápidos, que provamos ser NP-difícil. Este é um trabalho conjunto com Daniela Bubboloni, Costanza Catalano e Andrea Marino. Foi apresentado no FCT 2023, em Trier, Alemanha.

• Data e horário: 06/10/2023 às 13hs.
• Local: sala 3 do Bloco 914.
• Palestrante: Michael Souza.
• Título: Da Escassez à Abundância?
• Resumo: Nesta palestra de divulgação científica, será abordado o potencial emergente do ChatGPT como ferramenta inovadora para ganhos de escala na educação. Também serão abordados recentes avanços na área de processamento de linguagem natural.

• Data e horário: 29/09/2023 às 13hs.
• Local: sala 3 do Bloco 914.
• Palestrante: Allen Ibiapina.
• Título: Caminhos disjuntos em tempo em grafos temporais.
• Resumo: Um grafo temporal com tempo de vida τ é um par (G, L) onde L é uma função rótulo nas arestas de G que nos dizem em quais intervalos de tempo em [τ ] cada aresta estará ativa. Isto pode modelar, por exemplo, os momentos em que a comunicação direta entre os nós de uma rede foi estabelecida ao longo de uma janela de tempo. Muitas outras situações práticas podem ser modeladas em um grafo temporal, desde redes de proximidade, até transporte público e transações de bitcoin. Neste seminário, apresentaremos um novo tipo de robustez nesses grafos junto com resultados de complexidade computacional de problemas relacionados.
  Este trabalho foi feito em colaboração com Ana Shirley Silva e recebeu prêmio de melhor artigo estudantil no SAND 2023 (Pisa, Italia).

• Data e horário: 13/09/2023 às 13hs.
• Local: sala de seminários do Bloco 952
• Palestrante: Pedro Paulo de Medeiros (doutorando orientado pelo Prof. Júlio Araújo, PGMAT)
• Título: Os números de fecho e de  intervalo de orientações de grafos.
• Resumo: Neste trabalho, seja D um grafo orientado, estudamos seu número de intervalo e número de envoltória, denotados por \oin(D) e \ohn(D), respectivamente, na geodésica orientada, convexidades P_3 e P_3* orientadas. Esta última, acreditamos ter sido formalmente definida e estudada pela primeira vez neste artigo, embora sua versão não direcionada seja bem conhecida na literatura. Com relação aos limitantes, para um grafo orientado D fortemente conexo na convexidade geodésica orientada, provamos que \ohng(D)<= m(D)-n(D)+2 e que existe pelo menos um grafo orientado D tal que \ohng(D) = m(D)-n(D). Também determinamos valores exatos para os números de envoltória nessas três convexidades para torneios, o que implicam algoritmos com tempo polinomial para calculá-los. Esses resultados nos permitem deduzir algoritmos com tempo polinomial para calcular \ohnp(D) quando o gráfico subjacente de D é split ou cobipartido. Além disso, fornecemos um meta-teorema provando que decidir se \oing(D)<= k ou \ohng(D)<= k é NP-hard ou W[i]-hard parametrizado por k, para algum i em Z*_+, então o mesmo vale mesmo se o gráfico subjacente de D for bipartido. Provamos que decidir se \ohnp(D)<= k ou \ohnps(D)<= k$ é W[2]-hard parametrizado por k, mesmo que o gráfico subjacente de D seja bipartido; decidir se \oinp(D)<= k ou \oinps(D)<=k$ é NP-completo, e o mesmo para \ohnps(D)<= k mesmo que D não tenha ciclos direcionados e o gráfico subjacente de D seja um gráfico bipartido cordal; decidir se \oinp(D)<= k, e o mesmo para \oinps(D)<= k$ é W[2]-hard parametrizado por k, mesmo que o grafo subjacente de D seja split. Finalmente, mostramos também que o número de intervalo e número de envoltória nas convexidades P_3 e P_3* orientadas podem ser calculadas em tempo polinomial para grafos com largura em árvore limitada usando o Teorema de Courcelle.

• Data e horário: 01/09/2023 às 13hs.
• Local: Sala 2 do Bloco 952.
• Palestrante: Claro Henrique Silva Sales (mestrando orientado pelo Prof. Heron, MDCC).
• Título: Treino Distribuído de Redes Neurais Profundas: Alternativas e Desafios.
• Resumo:  Modelos de Deep Learning têm sido amplamente utilizados para o avanço de diversos campos da ciência, tornando-se a solução no estado da arte para problemas como reconhecimento de imagens, processamento de linguagem natural, dentre outros. Por outro lado, o crescimento da disponibilidade de dados e o avanço dos algoritmos trouxe uma demanda cada vez maior por capacidade computacional para o treinamento de redes neurais profundas (DNNs). Não é incomum que o treino de um modelo para aplicações reais demore dias, semanas ou até meses. Atualmente, o processamento paralelo é a principal estratégia para a aceleração do treino de DNNs. Além do paralelismo local, onde as tarefas são distribuídas entre uma ou mais CPUS e aceleradores, tais como GPUs, TPUS e FPGAs, de um único computador individual, equivalente a um nó de um cluster, a distribuição do processamento entre vários nós de um cluster, ou múltiplos clusters, têm se tornado uma prática comum para se permitir alcançar bons resultados em um tempo viável. Intuitivamente, a colaboração de vários aceleradores para realização do treino em um ambiente de processamento paralelo distribuído deve reduzir o tempo total do processo. No entanto, os custos relacionados à comunicação e sincronização geralmente limitam o ganho de velocidade. Por exemplo, o tempo de execução do treino distribuído entre vários aceleradores pode se tornar mais lento que o treino em um único acelerador, caso a conexão entre eles seja lenta. Em outros casos, o modelo de Deep Learning pode ocupar mais espaço de memória do que o suportado por uma única máquina, obrigando a divisão e distribuição de partições do modelo entre os diferentes aceleradores. Neste seminário apresentaremos uma introdução ao treino distribuído de redes neurais e discutiremos as suas principais alternativas e desafios de pesquisa.

• Data e horário: 18/08/2023 às 13hs.
• Local: Sala 3 do bloco 914.
• Palestrante: Andrea Marino (Universitá degli Studi di Firenze).
• Título: Optimal Paths in Temporal Graphs (palestra em inglês).
• Resumo: 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.

• Data e horário: 29/06/2023 às 13hs.
• Local: Sala de seminários do Bloco 952.
• Palestrante: Carla Negri Lintzmayer (UFABC).
• Título: Um passeio por algoritmos de aproximação para o TSP (e algumas de suas utilidades).
• Resumo: Nesse seminário darei uma breve introdução a algoritmos de aproximação e também apresentarei alguns
  resultados mais recentes de problemas que tenho trabalhado.
  Essas duas partes da palestra dependem fortemente do famoso Problema do Caixeiro Viajante (TSP).

• Data e horário: 26/06/2023 às 8hs.
• Local: Sala de seminários do Bloco 952.
• Palestrante: Allen Ibiapina (Defesa de doutorado, orientado por Ana Shirley F. Silva).
• Título: Teorema de Menger e Problemas Relacionados em Grafos Temporais (palestra em inglês).
• Resumo: Grafos temporais são uma ferramenta importante para modelar relacionamentos que variam com o tempo em sistemas dinâmicos. Entre os problemas de interesse, os problemas de caminhos e conectividade tem sido os que mais atraíram a atenção da comunidade. O famoso Teorema de Menger diz que, para cada par de vértices não adjacentes s, z em um grafo G, o número máximo de caminhos internamente disjuntos entre s e z em G é igual ao número mínimo de vértices em G\ {s, z} cuja remoção destrói todos os caminhos entre s e z (chamado de s,z-corte). Isso, combinado com técnicas de fluxo, também leva a algoritmos polinomiais para calcular caminhos disjuntos e cortes. Uma questão natural, portanto, é se tais resultados se aplicam a grafos temporais, onde os caminhos/passeios entre um par de vértices devem respeitar o fluxo do tempo. Nesta tese, investigamos três possíveis tipos de robustez, cada um dos quais leva a definições de dois parâmetros de otimização, um relacionado ao número máximo de caminhos disjuntos e o outro ao tamanho mínimo de um corte. Apresentamos resultados teóricos sobre a validade do Teorema de Menger e resultados de complexidade computacional para os problemas de decisão relacionados a cada parâmetro.

• Data e horário: 23/06/2023 à 13hs.
• Local: Sala 3 do Bloco 914 (Departamento de Matemática).
• Palestrante: Walner Mendonça.
• Título: Ramsey-bondade em grafos densos.
• Resumo: Dizemos que um grafo $G$ é Ramsey para o par de grafos \((F,H)\), se
  em toda coloração das arestas de $G$ com as cores vermelha e azul,
  existe uma cópia vermelha de $F$ ou uma cópia azul de $H$. Chvátal
  mostrou que o grafo completo $K_n$ é Ramsey para o par $(K_r,P_t)$,
  para $n \geq (r-1)(t-1) + 1$. Neste seminário, generalizaremos o
  teorema de Chvátal mostrando que para qualquer grafo $G$ com $n
  =(r-1)(t-1) + 1$ vértices e $\delta(G)\geq n – t/2$, temos que $G$ é
  Ramsey para $(K_r,P_t)$. Com este resultado, iniciamos o estudo de
  Ramsey-bondade em grafos densos.

• Data e horário: 16/06/2023 às 9hs.
• Local: Online.
• Palestrante: Emanuel Castelo (defesa de mestrado, orientado por Rafael Castro de Andrade).
• Título: Contribuições para o problema do caminho mínimo k-colorido
• Resumo: Dado um dígrafo D = (V, A), onde todos os arcos (i, j) em A possuem um custo d_{ij} real positivo e uma cor c(i, j), um inteiro positivo k, e vértices s e t em V, o Problema do Caminho Mínimo k-Rotulado consiste em encontrar um caminho de s para t em D de custo mínimo usando no máximo k cores de arcos distintas. Propomos desigualdades válidas para o problema que provaram fortalecer a relaxação linear de uma formulação existente na literatura de Programação Linear Inteira. Um conjunto exponencial de desigualdades válidas definem uma nova formulação para o problema, os quais são resolvidas utilizando um algoritmo de branch-and-cut. Introduzimos instâncias mais desafiadoras para o problema e apresentamos experimentos numéricos para as benchmark e as novas instâncias. Finalmente, nós avaliamos o uso individual e coletivo das desigualdades válidas. Resultados computacionais para as ideias propostas e para as abordagens existentes para o problema mostram a eficiência das novas desigualdades em lidar com as novas instâncias ambos em termos de tempo de execução e em proporcionar melhoria nas soluções relaxadas.

• Data e horário: 02/06/2023 às 13hs.
• Local: Sala 3 do Bloco 914 (Departamento de Matemática).
• Palestrante: Alexandre Cezar (aluno de doutorado, PGMAT).
• Título: Sobre orientações próprias (acíclicas) e produto cartesiano de grafos.
• Resumo: Dada uma orientação D das arestas de um grafo simples G, o grau de entrada de um vértice v de G, d_{D}^-(v), é o número de arcos que entram em v. Tal orientação induz uma coloração \phi(v) = d_{D}^{-}(v) de G. Dizemos que D é uma k-orientação própria se \phi é uma (k+1)-coloração própria de G. O número de orientação própria de G, denotado por \overrightarrow{\chi}(G), é o menor inteiro positivo k para o qual G admite uma k-orientação própria.
  Estudamos uma variação deste problema em que a orientação D é acíclica. Até onde sabemos, este é o primeiro artigo sobre esta variante. Além disto, estudamos também o parâmetro \overrightarrow{\chi} para grafos obtidos pelo produto cartesiano de outros grafos, introduzindo o conceito de conjunto caótico de orientações próprias, que é um conjunto de orientações próprias para as quais cada vértice possui graus de entradas diferentes em orientações diferentes.

• Data e horário: 25/05/2023 às 13hs.
• Local: Sala de reuniões do Bloco 952.
• Palestrante: Jonas Costa Ferreira da Silva (Defesa de Tese de Doutorado).
• Título: Estudo estrutural e de complexidade de Inversões e Heurísticas de Coloração de grafos (orientados).
• Resumo: Esta tese está dividida em duas partes. A primeira trata do número de inversão de grafos orientados.
  Seja D um grafo orientado. A inversão de um conjunto de vértices X ⊆ V(D) em D consiste na reversão da orientação de todos os arcos com ambas as extremidades em X. O número de inversão de D, denotado por inv(D), é dado pelo menor número de inversões necessárias para que D se torne acíclico. Nós estudamos limites e propriedades do número de inversão bem como a complexidade de computar este parâmetro.
  A segunda parte aborda colorações b-gulosas e z-colorações, que são heurísticas obtidas pela combinação de colorações gulosas e b-colorações. O número b-cromático de Grundy (resp.  z-cromático) de um grafo G é o maior inteiro k tal que G admite uma coloração b-gulosa (resp. z-coloração) com k cores, isto é, o pior caso desta heurística para o grafo G. Nós provamos que é NP-difícil obter cada um desses parâmetros e estudamos o seu comportamento em algumas classes de grafos.

• Data e horário: 24/05/2023 às 13hs.
• Local: Sala de reuniões do Bloco 952.
• Palestrante: Prof. Celina Figueiredo (UFRJ).
• Título:  A Perfect from Computational Biology to Quantum Computing.
• Resumo:  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.

• Data e horário: 12/05/2023 às 13hs.
• Local: Sala de reuniões do Bloco 952.
• Palestrante: Prof. Victor Campos.
• Título: Novas dualidades tipo Menger para digrafos com aplicações ao problema de linkage meio inteiro.
• Resumo: Apresentamos novas relações min-max em digrafos entre o número máximo de caminhos que satisfaz algumas propriedades e a ordem de cortes correspondentes. Definimos estes objetos para capturar as propriedades essenciais de conexão de um conjunto de terminais a uma estrutura fortemente conectada como um bramble ou um gride cilíndrico, ferramenta utilizada em soluções do problema de linkage meio inteiro. Esta estratégia tem sido utilizada em múltiplos resultados, normalmente com demonstrações longas e técnicas, e nosso objetivo é apresentar abstrações para serem utilizadas de uma forma simples e unificada. Apresentamos duas demonstrações para as relações min-max, uma mais simples mostrando como representar os problemas por interseção e união de matroides e uma outra que gera algoritmos melhores transformando os problems numa aplicação do Teorema de Merger em digrafos auxiliares.Como aplicação dos nossos resultados, mostramos como simplificar e melhorar alguns resultados de Edwards et al. [ESA 2017] e de Giannopoulou et al. [SODA 2022] sobre como achar linkages meio inteiros. Relativo ao resultado de Edwards et al. [ESA
  2017], além de mais simples, nossa demonstração apresenta um limitante quase ótimo para a conectividade forte de um digrafo que garante a existência de um linkade meio inteiro para qualquer conjunto de terminais quando o digrafo tem um bramble de ordem grande (de forma equivalente, que tem largura em árvore direcionada grande, que é o caso mais difícil das demonstrações). Relativo ao resultado de Giannopoulou et al. [SODA 2022], nossa demonstração é mais simples e utiliza brambles ao invés de grides cilíndricos para roteamento. Além de mostrar o mesmo tipo de roteamento com uma estrutura mais fraca, esta mudança oferece melhores limitantes para o tamanho da largura em árvore direcionada necessária para a sua aplicação. Esperamos que as estruturas apresentadas sejam aplicaveis a mais problemas de roteamento em digrafos por serem, na opinião dos coautores, simples, robustas e versáteis.Este trabalho foi realizado em coautoria com Jonas Costa, Raul Lopes e Ignasi Sau.

• Data e horário: 28/04/2023 às 13hs.
• Local: Sala de seminários do Bloco 952.
• Palestrante: Prof. Rudini Sampaio.
• Título: Códigos de Identificação em Grades Hexagonais.
• Resumo: Um conjunto C de vértices de um grafo é um código de identificação (ou idcode) se, para todo vértice v, C[v] não é vazio e, para quaisquer vértices distintos u e v, C[u] e C[v] são diferentes, onde C[v]=N[v]\cap C e N[v] denota a vizinhança fechada de v. Seja d(G) a densidade mínima de um idcode de G. Um dos maiores problemas em aberto nessa área é a densidade mínima da grade hexagonal infinita, que se conjectura ser 3/7=0.42857. Nesse seminário, nós iniciamos a investigação de idcodes mínimos de grades hexagonais cíclicas com k linhas, denotado por H*_k, que são úteis pois seus idcodes podem ser usados para obter idcodes da grade infinita com a mesma densidade. Apenas cinco idcodes com densidade 3/7 da grade infinita eram conhecidos: um do H*_2, dois do H*_4, um do H*_6 e um do H*_7. Em 2004, Daniel et al. provaram que d(H*_2)=3/7. Nesse seminário, nós combinamos o método da descarga com uma abordagem para grades com número limitado de linhas a fim de obter um prova assistida por computador de que d(H*_3)=0.44 e d(H*_4)=d(H*_5)=3/7, o que reforça a conjectura da densidade 3/7. Nós também provamos que, além dos cinco idcodes conhecidos, existem infinitos idcodes periódicos com densidade 3/7 para a grade infinita, incluindo os primeiros provenientes do H*_5. Finalmente, nós também provamos que d(H_2)=9/20=0.45, d(H_3)=6/13=0.4615, d(H_4)=7/16=0.4375, d(H_5)=0.44, d(H_6)\leq 0.4375 e d(H_{7p})\leq 3/7 para todo p\geq 1, onde H_k é a grade infinita com k linhas. Este trabalho foi feito em colaboração com a Prof. Yoshiko Wakabayashi (USP) e seu aluno de doutorado Gabriel Sobral. Recebeu o prêmio de melhor resumo no VII Encontro de Teoria da Computação – ETC 2022.

• Data e horário: 14/04/2023 às 13hs.
• Local: Sala de reuniões do Bloco 910 (Dep. de Estatística e Dep. de Computação)
• Sessão de problemas em aberto.

• Data e horário: 31/03/2023 às 13hs.
• Local: Sala 3 do bloco 914.
• Palestrante: Pierre Aboulker (TALGO – École Normale Supérieure de Paris).
• Título: Induced subdigraphs of digraphs with large dichromatic number (apresentação em inglês).
• Resumo: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.

• Data e horário: 22/03/2023 às 13hs (quarta-feira).
• Local: Sala 3 do bloco 914.
• Palestrante: Raul Lopes (TALGO – École Normale Supérieure de Paris).
• Título: Twin-width VIII: delineation and win-wins (apresentação em inglês).
• Resumo: 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.

• Data e horário: 17/03/2023 às 13hs.
• Local: Sala 3 do bloco 914.
• Sessão de problemas em aberto.

2022

• Data e horário: 16/12/2022 às 13hs.
• Local: Online.
• Palestrante: Prof. Andrea Marino (Universitá degli Studi di Firenze).
• Título: On Computing the Diameter of (Weighted) Link Streams
• Resumo: A weighted link stream is a pair (V,E) comprising V, the set of nodes, and E, the list of temporal edges (u,v,t,\lambda), where u,v are two nodes in V, t is the starting time of the temporal edge, and \lambda is its travel time. By making use of this model, different notions of diameter can be defined, which refer to the following distances: earliest arrival time, latest departure time, fastest time, and shortest time. After proving that any of these diameters cannot be computed in time sub-quadratic with respect to the number of temporal edges, we propose different algorithms (inspired by the approach used for computing the diameter of graphs) which allow us to compute, in practice very efficiently, the diameter of quite large real-world weighted link stream for several definitions of the diameter. In the case of the fastest time distance and of the shortest time distance, we introduce the notion of pivot-diameter, in order to deal with the fact that temporal paths cannot be concatenated in general. The pivot-diameter is the diameter restricted to the set of pairs of nodes connected by a path which passes through a pivot (that is, a node at a given time instant). We prove that the problem of finding an optimal set of pivots, in terms of the number of pairs connected, is NP-hard, and we propose and experimentally evaluate several simple and fast heuristics for computing “good” pivot sets.

• Data e horário: 18/11/2022 às 13hs.
• Local: Sala 03 do Bloco 914.
• Palestrante: Prof. Nicolas Nisse (COATI – INRIA Sophia-Antipolis, França).
• Título: Tree and Path decompositions with small diameter bags in subclasses of planar graphs.
• Resumo: Tree/Path decompositions are usually viewed as a way to decompose a graph along small separators. Another possible measure is the diameter of the separators rather than their size. Precisely, the length of a tree-decomposition of a graph G is the maximum diameter of its bags, where the diameter of a bag B equals the maximum of the distance (in G) between any two vertices in B. The treelength (resp., pathlength) of G is the minimum length of its tree/path decompositions. Several metric problems (metric dimension, TSP, compact routing…) can be solved efficiently in bounded tree/path length graphs. Deciding whether a graph has tree/path length at most 2 is NP-complete and there is no 3/2-approximation for treelength unless P=NP. We investigate the complexity of computing these parameters in subclasses of planar graphs such that outerplanar graphs or series-parallel graphs. This talk summarizes joint works with Thomas Dissaux, Guillaume Ducoffe and Simon Nivelle.

• Data e horário: 04/11/2022 às 13hs.
• Local: Sala 03 do Bloco 914.
• Palestrante: Ignasi Sau (LIRMM – Montpellier, França).
• Título: Graph modification problems with forbidden minors
• Resumo: In a generic graph modification problem, given an input graph G, the goal is to apply some modifications to it, belonging to a prescribed set M (say, vertex deletion or edge contraction), in order to obtain a graph that belongs to a target graph class C (say, a planar graph or a 3-regular graph). Different instantiations of M and C yield a number of well-studied problems such as Vertex Cover or Feedback Vertex Set. A very active line of research studies the parameterized complexity of this family of problems for various choices of the parameter. Of particular relevance is the case where the target graph class C excludes some graph as a minor. In this talk I will survey recent work in this direction, along with some of the most common techniques used in the literature.

• Data e horário: 07/10/2022 às 13hs.
• Local: Sala de seminários do bloco 952.
• Palestrantes: Ana Beatriz Martins e Rayane Castro (orientandas do Prof. Júlio).
• Títulos e resumos:
  • Beatriz – Coloração Harmoniosa: Uma k-coloração  c:V(G)→ {1,2,…,k}  é uma  coloração linha-distinguível se cada par de arestas distintas têm conjuntos de cores distintas em suas extremidades.  O número cromático linha-distinguível de G é λ(G) = min{k∈N|G tem uma k-coloração linha-distinguível}. Se uma coloração linha-distinguível c é própria, então c é uma coloração harmoniosa. O número cromático harmonioso, denotado por h(G), é o menor k∈N tal que G tem uma k-coloração harmoniosa. Neste trabalho, apresentamos uma condição necessária e suficiente para h(G) ser k, para um grafo arbitrário e k∈N. Após isso, apresentamos formulações de programação inteira para computar h(G) e alguns testes preliminares em grafos aleatórios com densidades de arestas distintas.
    Este trabalho foi feito em colaboração com Júlio Araújo (orientador) e Márcio C. Santos.
  • Rayane – Galáxias como backbone em colorações backbone: dados um inteiro q≥2, um grafo simples G e um subgrafo gerador H, o número cromático (circular) q-backbone, denotado por BBCq(G,H) (resp. CBCq(G,H)), é o  menor  inteiro k tal que G tem uma k-coloração própria f satisfazendo que se uv∈E(H),  então |f(u)−f(v)| ≥q (resp. k−q≥ |f(u)−f(v)| ≥q).  Neste trabalho, mostramos que para grafo G planar e M um emparelhamento, então CBCq(G,M) ≤ q+ 5, para q∈{2,3}, sem usar o Teorema das Quatro Cores.  Além disso, nós corrigimos um lema apresentado em Havet, King, Liedloff, e Todinca, (circular) backbone colouring: Forest backbones inplanar graphs, Discrete Applied Mathematics 169 (2014), 119–134. Este trabalho foi feito em colaboração com Júlio Araújo (orientador) e Alexandre Cezar.

• Data e horário: 23/09/2022 às 13hs.
• Local: online.
• Palestrante: Rodrigo Nogueira (orientando do Prof. Victor).
• Título: Instances for the Maximum Clique Problem with Hardness Guarantees
• Resumo: Branch and bound algorithms which use (an estimate on) the chromatic number as the bounding function are reported among the best known exact algorithms for the maximum clique problem. Their average running time is known to be quasi-polynomial and describing families of instances which induce exponential running time for these algorithms is a non-trivial issue. We describe two such families of graphs. We prove that graphs in the first family induce asymptotically higher running time than the average for algorithms whose running time is Ω(c(G)) where c(G) is the number of cliques in G. We also prove that graphs in the second family induce exponential running time for branch and bound algorithms which use the chromatic number as the bounding function. This work was done in collaboration with Victor Campos (advisor) and Renato Carmo (UFPR).

• Data e horário: 09/09/2022 às 13hs.
• Local: Sala de seminários do bloco 952.
• Palestrantes: Kenny Domingues e Davi de Andrade (orientandos da Profa. Ana Shirley)
• Títulos e resumos: 
  • Davi – (Sub)Fall Coloring and B-Coloring Parameterized by Treewidth: Dada uma coloração própria f de G, um vértice é dito b-vértice em f se possui pelo menos um vizinho em cada cor diferente da sua. Tal coloração  é uma b-coloração se cada cor contém pelo menos um b-vértice; e é uma fall coloração se todo vértice de G é b-vértice. Além disso, se f é uma fall coloração de um subgrafo induzido de G, então chamamos f de subfall coloração de G. Neste trabalho, fornecemos, para cada um destes problemas, algoritmos FPT parametrizados pelo número de cores somado com a largura em árvore do grafo de entrada.
  • Kenny – On the Partial Grundy Number of a Graph Minus a Matching: Given a k-coloring of G, a vertex in color i is said to be greedy if it has neighbors in color j , for every j < i. Thus, a Grundy coloring can be seen as a coloring where every vertex is greedy. In contrast, a partial Grundy coloring is defined as a coloring in which each color class has at least one greedy vertex; the maximum number of colors in a partial Grundy coloring is denoted by ∂Γ(G). In this paper, we investigate adaptations of some conjectures about Grundy colorings, these known not to hold. We prove that, while two of them also do not hold for partial Grundy colorings, a third one does. Namely, it holds that, given a graph G and a matching M of G, we have that ∂Γ(G)<=∂Γ(G-M).

• Data e horário: 26/08/2022 às 13hs.
• Local: Sala de seminários do bloco 952.
• Palestrante: Prof. Carlos Diego Rodrigues.
• Título: Otimizando o custo de manipulação de preferências no modelo de grafos para resolução de conflitos
• Resumo: Conflitos ocorrem quando diferentes partes têm diferentes avaliações em relação à resolução de algum problema e cada uma delas pode alterar o cenário do conflito de mais de uma forma. Em muitas situações, oferecer incentivos para alterar as preferências de alguns tomadores de decisão (DMs) pode ser uma maneira eficaz de alcançar cenários estáveis desejáveis. O Modelo de Grafos para Resolução de Conflitos (GMCR) é um modelo que há muito vem sendo utilizado para modelar e analisar conflitos por ser flexível e fácil de calibrar. O objetivo deste trabalho é apresentar ideias de como trabalhar com o GMCR inverso para otimizar custos na mudança das preferências de cada DM para alcançar estados de equilíbrio desejados dentro do conflito. Propomos alguns métodos para agregar custos de mudança de preferências dos DMs com a intenção de minimizar o custo agregado das mudanças de preferência que tornam um dado estado desejado um equilíbrio de acordo com uma dada noção de estabilidade. Além de descrever formalmente o problema, estudamos algumas propriedades dos custos mínimos para diferentes noções de estabilidade e mostramos que a complexidade computacional do problema de manipulação de preferência ótima é NP-difícil. Mostramos também como estes conflitos podem ser modelados de forma eficiente como problemas de otimização inteira.

• Data e horário: 08/07/2022 às 14hs.
• Local: Online.
• Projeção na sala de seminários do bloco 952.
• Palestrante: Prof. Heron Carvalho.
• Título: A Programação Ciente-de-Plataforma e sua Implementação em Julia
• Resumo: Apresentaremos a programação ciente-de-plataforma (platform-aware programming), cujo objetivo é promover a coexistência modular entre várias versões de partes constituintes de um programa que possuem alta demanda computacional, chamadas de kernels, de acordo com diferentes suposições sobre a sua plataforma de execução alvo. Defendemos que a programação ciente-de-plataforma beneficia aplicações que usam a computação heterogênea para atender a requisitos de computação de alto desempenho (HPC), uma vez que os programadores podem usar as interfaces de programação mais eficientes para um determinado dispositivo acelerador de maneira modular, evitando preocupações com a portabilidade de código e com a sobrecarga no desempenho característica de interfaces de programação genéricas. Relataremos o porquê e como a programação ciente-de-plataforma tem sido implementada por nós na linguagem Julia aproveitando seu mecanismo de despacho múltiplo, auxiliando os desenvolvedores de pacotes com requisitos de HPC sem impacto aos seus usuários.

• Data/horário: 24/06 -14hs.
• Local: sala de seminários do bloco 952.
• Palestrante: Emanuel Elias.
• Pré-proposta de dissertação de mestrado MDCC – UFC, aluno orientado pelo Prof. Rafael Andrade.
• Título: O problema do caminho mínimo k-rotulado.
• Resumo: Seja um digrafo D = (V, A, c, d) em que  cada arco (i,j) de A possui uma cor e um custo. Dados um nó origem s e um nó destino t de V, desejamos encontrar um (s,t)-caminho p* de custo mínimo em D, onde a quantidade de cores distintas dos arcos de p* seja no máximo um k natural. Apresentamos novas desigualdades válidas para o problema, uma formulação alternativa de programação linear inteira com base nas cores fora do caminho e duas classes de instâncias difíceis para o problema baseadas em trabalhos existentes. Comparamos resultados computacionais para um modelo da literatura e analisamos o impacto das novas desigualdades tanto para esse modelo quando para o modelo alternativo com base em instâncias benchmark da literatura e nas novas instâncias.

• Data/horário: 27/05 e 10/06 – 14hs.
• Local: sala de seminários do bloco 952.
• Palestrante: Prof. Fabrício Siqueira Benevides.
• Título: Maximizing the expected number of components in an online search of a graph.
• Resumo: The following optimal stopping problem is considered. The vertices of a graph G are revealed one by one, in a random order, to a selector. He aims to stop this process at a time t that maximizes the expected number of connected components in the graph G_t, induced by the currently revealed vertices. The selector knows G in advance, but different versions of the game are considered depending on the information that he gets about G_t. We show that when G has N vertices and maximum degree of order o(sqrt{N}), then the number of components of G_t is concentrated around its mean, which implies that playing the optimal strategy the selector does not benefit much by receiving more information about G_t. We also consider the particular cases where G is a square, triangular or hexagonal lattice, showing near optimal estimates for the expected number of components.

• Data/horário: 29/04 e 13/05/2022 – 14hs.
• Local: sala de seminários do bloco 952.
• Palestrante: Prof. Manoel Campelo
• Título: Connections between the flow coloring problem and the minimum maximum flow degree problem.
• Resumo: Consider an arc-capacitated network G through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multigraph with the same vertices as G and an edge for each arc of G, where the edge multiplicity is the flow in the respective arc. The flow coloring problem (FCP) consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index, to be called flow chromatic index. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of G, i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining a feasible flow such that its maximum flow degree is minimum. The two problems are closely related. We recapitulate some results on FCP, including polynomial algorithms and approximation algorithms for some cases.  For MMFDP, we present a polynomial time algorithm as well an ILP formulation that can be solved in polynomial time. We explore the relations between the two problems. We present lower and upper bounds for FCP based on the minimum maximum flow degree. We also comment on an approximation algorithm for FCP based on the algorithm for MMFDP.

• Data/horário: 08/04/2022 – 13hs.
• Local: sala 1035, bloco 915.
• Palestrante: Ronan Soares.
• Título: Javascript – “a linguagem da Internet”.
• Resumo: Se você já sabe programar, aprenda Javascript em ± 25min…

• Data/horário: 17/03/2022 – 9hs.
• Local: Online.
• Palestrante: Alexandre Azevedo Cezar (doutorando – PGMAT).
• Título: Um Estudo de Orientação Própria e Coloração Backbone.
• Resumo: (Defesa de proposta de teste) Dado um grafo G = (V, E), uma k-coloração própria é uma função φ de V  em {1,…,k} em que φ(u) ≠φ(v), para toda aresta uv de G. Neste texto, estudamos dois tipos de colorações próprias de grafos: a Orientação Própria e a Coloração Backbone.Para um grafo G, uma orientação D é um digrafo obtido substituindo-se cada aresta de G por um dos arcos possíveis com as mesmas extremidades. O grau de entrada de um vértice v é o número de arcos de D com cabeça em v. A orientação é dita própria se o grau de entrada de u é distinto do de v para toda aresta uv em G. Se k é o maior grau de entrada de um vértice na orientação D, dizemos que D é uma k-orientação. O número de orientação própria de G, ρ(G), é o menor valor de k para o qual existe uma k-orientação própria. Note que uma k-orientação própria nos dá uma (k+1)-coloração própria de G.Dado um subgrafo H de um grafo G, q e k inteiros positivos, uma q-backbone k-coloração do par (G,H) é uma k-coloração própria φ em que também é satisfeito q ≤ |φ(u) – φ(v)|, para cada aresta uv de H. Fixado q, o número cromático q-backbone do par (G,H) é o menor valor de k para o qual existe esta coloração. Similarmente, uma q-backbone k-coloração circular do par (G,H) é uma coloração própria φ em que também é satisfeito q ≤ |φ(u) – φ(v)| ≤ k-q, para cada aresta uv de H. Fixado q, o número cromático q-backbone circular do par (G,H) é o menor valor de k para o qual existe esta coloração.

• Data/horário: 21/02/2022 – 9hs.
• Local: Online.
• Palestrante: Leonardo Cavalcante de Abreu (defesa de TCC)
• Título: PROBLEMA DO SUBGRAFO ACÍCLICO MÁXIMO SUJEITO A RESTRIÇÕES DE CONFLITO: ESTUDO DE COMPLEXIDADE EM INSTÂNCIAS DE GRAU LIMITADO
• Resumo: O Problema do Subgrafo Acíclico Máximo sujeito a Restrições de Conflito (MASCC) — do inglês maximum acyclic subgraph problem — consiste em, dado um grafo direcionado D = (V, A) e um grafo de conflitos G = (A,E), encontrar um subconjunto A′ ⊆ A de cardinalidade máxima tal que o subgrafo induzido por A′ em D seja acíclico e A′ seja conjunto independente em G. Conseguimos caracterizar uma dicotomia entre casos polinomiais e NP-Difíceis do problema, em função dos graus máximos de D e G. Mostramos que o MASCC é NP-Difícil se min{∆(D), ∆(G)} ≥ 2 ou max{∆(D), ∆(G)} ≥ 3, e que é polinomial caso contrário. Para isso, apresentamos uma redução de 3-SAT que mostra o caso NP-Difícil e um algoritmo polinomial que resolve o caso complementar. Apresentamos também um algoritmo (2.5/(3 + ∆(G))) aproximativo para o problema e um algoritmo aproximativo de fator log log ∆(G)/O(∆(G)) para o MASCC, estendendo resultados da literatura.

• Data/horário: 08/02/2022 – 13hs.
• Local: Online.
• Palestrante: Allen Ibiapina (doutorando – PGMAT)
• Título: Mengerian Temporal Graphs Revisited
• Resumo: A temporal graph is a graph together with a time labeling function that tells when each edge of the graph is active. It is known that Menger’s Theorem does not hold on temporal graphs, i.e., that the maximum number of internally vertex disjoint temporal s,t-paths is not necessarilly equal to the minimum size of a size of an s,t-cut. In a seminal paper, Kempe, Kleinberg and Kumar (STOC’2000) defined a graph G to be Mengerian if equality holds on (G,\lambda) for every time-labeling \lambda. They then proved that, if each edge is allowed to be active only once in (G,\lambda), then G is Mengerian if and only if G has no gem as topological minor. In this work, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm.

• Data/horário: 25/01/2022 – 13hs.
• Local: Online.
• Palestrante: Márcio Santos Costa. (UFC – Russas)
• Título: Formulações para modelar colorações harmônicas e harmoniosas em grafos.
• Resumo: Dado um grafo G=(V,E), uma coloração é uma atribuição de cores aos vértices de G. Diversas variações desse conceito foram estudados em computação ao longo dos anos, para citar alguns: se vértices adjacentes devem ter cores diferentes dizemos que a coloração é própria e, se além de própria cada classe de cor (conjunto de vértices da mesma cor) tem pelo menos um vizinho em todas as demais classes de cor, dizemos que essa é uma a-coloração.Uma coloração harmônica é uma coloração onde não existem duas arestas com o mesmo par de cores em seus extremos. Dito de outra forma, uma coloração é harmônica se ela identifica as arestas do grafo de maneira única através das cores de seus extremos. Se, além de harmônica, a coloração é própria, dizemos que ela é harmoniosa.O tema de coloração harmônica vem sendo estudado sobre o prisma de teoria dos grafos, mas quase nenhum trabalho existe sobre o prisma de pesquisa operacional. Nesse sentido, apresentamos duas formulações para modelar problemas que envolvem colorações harmônicas e harmoniosas, em especial para o problema de determinar o número harmônico cromático de um grafo (o menor número de cores necessários para colorir o grafo com uma coloração harmônica).

• Data/horário: 14/01/2022 – 9hs.
• Local: Online.
• Palestrante: Francisco Antonio Ferreira de Almeida.
• Título: Teoria Algorítmica de Matroides.
• Resumo: Defesa de proposta de dissertação do aluno. Neste trabalho realizamos um estudo teórico e algorítmico sobre matroides onde apresentamos desde os seus conceitos básicos, propriedades fundamentais, fórmulas min-max e os algoritmos de interseção e união de matroides e, finalmente, mostramos uma fórmula min-max para caracterização de um emparelhamento matroide máximo sobre o matroide gráfico. Para interseção e união de matroides, também apresentamos aplicações sobre grafos e transversais. O aluno foi orientado pelo Prof. Victor Campos, no âmbito do programa MDCC.

2021

• Data/horário: 07/12/2021 – 13hs.
• Local: Online.
• Palestrante: Rudini Sampaio.
• Título: O Jogo do Espião em Grafos.
• Resumo: No jogo (s,d) do Espião sobre um grafo G, um espião se posiciona em um vértice do grafo e depois k guardas se posicionam sobre vértices de G e, a cada turno, o espião pode se mover com velocidade s (ao longo de no máximo s arestas) e cada guarda pode se mover ao longo de uma aresta. O espião e os guardas podem ocupar os mesmos vértices. O espião ganha se alcançar um vértice a distância maior do que a distância de vigilância d de cada guarda. Este jogo foi introduzido por Cohen et al. em 2016 e está relacionado a dois jogos bem estudados: Jogo de Polícia e Ladrão em Grafos e o Jogo da Dominância Eterna. O número de guardas gn_{s,d}(G) é o número mínimo de guardas tal que os guardas tenham uma estratégia vencedora (de controlar o espião) no grafo G. Em 2018, foi provado que decidir se o espião tem uma estratégia vencedora é NP-difícil para cada velocidade s>=2 e distância d>=0. Neste artigo, nós iniciamos a investigação do número de guarda em grades e em produtos de grafos. Nós obtemos um limite superior para o produto forte de dois grafos quaisquer e obtemos exemplos com grades King que acertam esse limite e outros exemplos para os quais o número de guarda é menor. Também obtemos o valor exato do número de guarda no produto lexicográfico de dois grafos quaisquer para qualquer distância d>=2. Do ponto de vista algorítmico, provamos um resultado positivo: se o número k de guardas for fixo, o jogo do espião pode ser resolvido em tempo polinomial O(n^{3k + 2}) para cada velocidade s>=2 e distância d>=0. Em outras palavras, o jogo do espião é XP quando parametrizado pelo número de guardas. Este algoritmo XP é usado para obter um algoritmo FPT para grafos com poucos P4s. Como resultado negativo, provamos que o jogo do espião é W [2]-difícil mesmo em grafos bipartidos quando parametrizado pelo número de guardas, para qualquer velocidade s>=2 e distância d>=0, estendendo o resultado de dificuldade de Cohen et al. em 2018. Esse é um trabalho em conjunto com Eurinardo Costa e Nicolas Martins e foi apresentado no congresso COCOON-2021.

• Data/horário: 23/11/2021 – 13hs.
• Local: Online.
• Palestrante: Ana Shirley F. Silva
• Título: Corte máximo de grafos de intervalo.
• Resumo: O problema de corte máximo é um dos mais tradicionais e mais desafiadores na Teoria dos Grafos. Prova é que, mesmo em grafos de intervalo, o problema permaneceu em aberto até apenas muito recentemente, quando foi provado ser NP-completo (Adhikary et al., 2021). O número de intervalo de um grafo de intervalo é igual à quantidade mínima de tamanhos de intervalos necessária para modelar o grafo. A complexidade do problema restrito a grafos de intervalo com número de intervalo 1 (também chamados intervalo próprio) continua a desafiar a comunidade, já tendo havido ao menos duas provas incorretas de polinomialidade apresentadas ao longo dos anos. Neste trabalho, damos a primeira classificação para o problema restrito a grafos de intervalo com número de intervalo limitado. Estendendo a redução de Adhikary et al., mostramos que o problema continua NP-completo mesmo se o número de intervalo é no máximo 4. Este trabalho foi feito em colaboração com Celina Figueiredo (UFRJ), Alexsander Melo (UFRJ) e Fabiano Oliveira (UERJ), e foi apresentado no MFCS 2021.

• Data/horário: 09/11/2021 – 13hs.
• Local: Online.
• Palestrante: Guilherme Mota (USP).
• Título:Colorações restritas de grafos aleatórios
• Resumo: Dados grafos G, H_1 e H_2, seja G —> (H_1,H_2) a propriedade que em toda coloração das arestas de G temos uma cópia monocromática de H_1 ou uma cópia multicolorida (“rainbow”) de H_2. O número de Ramsey restrito, definido como o menor n tal que K_n —> (H_1,H_2), existe se e somente se H_1 é uma estrela ou H_2 é uma floresta.
  Nós estimamos a função limiar para a propriedade G(n,p) —> (H_1,H_2) quando H_2 é uma floresta.

• Data/horário: 26/10/2021 – 13hs.
• Local: Online.
• Palestrante: Carlos Diego Rodrigues
• Título: Formulação compacta baseada em faixas para problemas de corte guilhotinado bidimensional.
• Resumo: Os problemas de corte guilhotinado bidimensional (2D-GCP) são relevantes para diversas áreas da atividade humana, tais como a indústria móveleira, do vidro, granito, carregamento de paletes, desenvolvimento de circuitos integrados, etc. Apesar dos primeiros ensaios para formular estes problemas sejam tão antigos quanto a programação linear, os 2D-GCP só ganharam sua primeira formulação para o caso geral com Furini et al. 2016 para o problema da mochila bidimensional. Apresentamos uma formulação compacta capaz de modelar diversos problemas clássicos bidimensionais guilhotinados (corte de estoque, mochila, strip packing, etc.), cuja performance se mostrou competitiva com os modelos dedicados para problemas específicos.

• Data/horário: 19/10/2021 – 13hs.
• Local: Online.
• Palestrante: Andrea Marino (Universitá degli Studi di Firenze).
• Título: Approximating the Neighborhood Function of (Temporal) Graphs.
• Resumo: The average distance often referred to as degrees of separation, in graphs (like, for instance, the Facebook friendship network and the Internet Movie Database collaboration network) has been largely investigated. However, if the number of nodes is very large (millions or billions), computing this measure needs prohibitive time and space costs as it requires to compute for each node the so-called neighborhood function, i.e. for each vertex v and for each h, how many nodes are within distance h from v. Temporal graphs are a special kind of graphs where edges have temporal labels, specifying their occuring times, in the same way as the connections of the public transportation network of a city are available only at scheduled times. Here, paths make sense only if they correspond to sequences of edges with strictly increasing labels. A possible notion of distance between two nodes in a temporal network is the earliest arrival time of the temporal paths connecting the two nodes. In this case, the temporal neighborhood function is defined as the number of nodes reachable from a given one in a given time interval, and it is also expensive to compute. We introduce probabilistic counting in order to approximate the size of sets and we show how both plain and temporal neighborhood functions can be approximated by plugging this technique into a simple dynamic programming algorithm.

• Data/horário: 14/10/2021 – 13hs.
• Local: Online.
• Palestrante: Allberson Bruno de Oliveira Dantas (UNILAB).
• Título: Ciência de Dados com Grafos.

• Data/horário: 19/08/2021 – 16hs
• Local: Online
• Palestrante: Rafael Andrade.
• Título: Introdução às árvores de cristal.
• Resumo: O conceito de árvore de cristal tem origem em operações de multiconjuntos que definem potenciais de nós de uma árvore k-enraizada de um grafo ponderado conexo G=(V,E). O potencial de um nó é o conjunto formado pelos pesos das arestas no caminho da raiz até esse nó na árvore. Existem dois tipos de equilíbrio em relação a um par de nós ligados por uma aresta. Uma árvore é de cristal se todos seus pares de nós conectados por uma aresta estiverem em equilíbrio.

• Data/horário: 05/08/2021 – 16hs
• Local: Online
• Palestrante: Fabrício Siqueira Benevides.
• Título: On Heilbronn triangle-type problems in higher dimensions.
• Resumo: The Heilbronn triangle problem is a classical geometrical problem that asks for a placement of n points in the unit-square [0,1]^2, that maximizes the smallest area of a triangle formed by those points. This problem has natural generalisations to higher dimensions. For integers k, d > 1 and a set P of n points in [0,1]^d, let s be the minimum of (k-1) and d; and let V(k, d, P) be the minimum s-dimensional volume of the convex hull of k points in P. Here, instead of considering the supremum of V(k, d, P), we consider its average value, avrgDelta(k, d, n),  when the n points in P are chosen independently and uniformly at random in [0,1]^d. We prove that avrgDelta(k, d, n) is of order n to the power of (-k / {1 + |d-k+1| } ), for every fixed k, d > 1.

• Data/horário: 22/07/2021 – 16hs
• Local: Online
• Palestrante: Ronan Pardo Soares.
• Título: Git + GitHub (Pro) + LaTeX = Colaboração e Correção “sem” dor de cabeça
• Resumo: Como utilizar o Git + GitHub (Pro), uma ferramenta de controle de versão e um site de hospedagem, para realizar trabalhos colaborativos em LaTeX (ou não), se organizar, e garantir que feedbacks sejam devidamente integrados ao texto.

• Data/horário: 08/07/2021 – 16hs
• Local: Online
• Palestrante: Manoel Campêlo.
• Título: O problema de formação de múltiplas equipes
• Resumo: Dado um conjunto de indivíduos, cada um com uma habilidade/competência específica, e uma rede social captando a afinidade mútua entre eles, o Problema de Formação de Equipe (TFP – Team Formation Problem) visa encontrar uma única equipe que reúna as habilidades necessárias para realizar uma tarefa, enquanto busca otimizar os custos de comunicaçãoentre os indivíduos envolvidos. Neste trabalho, estudamos uma generalização do TFP denominada Problema de Formação de Múltiplas Equipes (MTFP – Multiple Team Formation Problem), que permite demandas distintas de trabalhadores para cada tipo de habilidade, assim como requisições de múltiplas equipes de trabalho e possibilidade de fracionamento do tempo de dedicação de cada indivíduo entre os times. Nesse caso, o custo total de comunicação é dado pela soma dos pesos das relações dos pares de indivíduos de um mesmo time. Propomos uma formulação de Programação Linear Inteira (ILP) e famílias de desigualdades válidas. Experimentos computacionais atestam que o modelo ILP fortalecido por desigualdades válidas supera consistentemente a formulação quadrática apresentada na literatura para resolução do MTFP. Também consideramos uma versão generalizada do MTFP em que os indivíduos podem ter múltiplas habilidades. Para lidar com esta versão, adaptamos o modelo ILP inicial, gerando dois novos modelos, um deles com mais variáveis e outro com um número exponencial de restrições, mas que mostramos serem separáveis em tempo polinomial. Também para o segundo problema, apresentamos um outro conjunto de desigualdades válidas que fortalecem os dois modelos.

Este trabalho foi desenvolvido em co-autoria com Tatiane Figueiredo (UFC-Russas).

• Data/horário: 27/05/2021 – 16hs
• Local: Online
• Palestrante: Vários
• Título: Sessão de Problemas

• Data/horário: 13/05/2021 – 16hs
• Local: Online
• Palestrante: Victor Campos.
• Título: Kernelization of Maximum Minimal Vertex Cover
• Resumo:In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex optimization problems, which we call lop-kernels. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP/poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.Este trabalho foi feito em conjunto com Júlio Araújo, Marin Bougeret e Ignasi Sau.

• Data/horário: 29/04/2021 – 16hs.
• Local: Online.
• Palestrante: Raul Lopes.
• Título: Adapting the Directed Grid Theorem into an FPT Algorithm.
• Resumo:  The Grid Theorem of Robertson and Seymour [JCTB, 1986] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001] , and proved by Kawarabayashi and Kreutzer [STOC, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter k, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor.In this talk, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D, improving on the original result for arboreal decompositions by Johnson et al. [JCTB, 2001]. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k that is contained in the set of vertices of a path hitting all elements of B. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|.

• Data/horário: 15/04/2021 – 16hs.
• Local: Online.
• Palestrante: Jonas Costa.
• Título: On the inversion number of oriented graphs.
• Resumo: Let D be an oriented graph. The inversion of a set X of vertices in D consists in reversing the direction of all arcs with both ends in X. The inversion number of D, denoted by inv(D), is the minimum number of inversions needed to make D acyclic. Denoting by τ(D), τ 0 (D), and ν(D) the cycle transversal number, the cycle arc-transversal number and the cycle packing number of D respectively, one shows that inv(D) ≤ τ 0 (D), inv(D) ≤ 2τ(D) and there exists a function g such that inv(D) ≤ g(ν(D)). We conjecture that for any two oriented graphs L and R, inv(L → R) = inv(L) + inv(R) where L → R is the dijoin of L and R. This would imply that the first two inequalities are tight. We prove this conjecture when inv(L) ≤ 1 and inv(R) ≤ 2 and when inv(L) = inv(R) = 2 and L and R are strongly connected. We also show that the function g of the third inequality satisfies g(1) ≤ 4. We then consider the complexity of deciding whether inv(D) ≤ k for a given oriented graph D. We show that it is NP-complete for k = 1, which together with the above conjecture would imply that it is NP-complete for every k. This contrasts with a result of Belkhechine et al. (BELKHECHINE et al., 2010) which states that deciding whether inv(T ) ≤ k for a given tournament T is polynomial-time solvable.

• Data/horário:  18/03/2021 – 16hs
• Local: Online
• Palestrante: Rudini Sampaio
• Título: Jogo de Coloração em Grafos e suas variantes
• Resumo: Em 1991, Bodlaender introduziu o jogo de coloração em grafos e deixou uma pergunta em aberto sobre a complexidade computacional desse problema. Essencialmente, Alice e Bob  colorem os vértices de um grafo usando um conjunto de cores, com Alice iniciando o jogo. Se o grafo é inteiramente colorido, Alice vence. Caso contrário, Bob vence. Em 2009, outras variantes foram introduzidas, permitindo a Bob iniciar o jogo e/ou permitindo a um deles pular jogadas, bem como obrigando que a coloração seja gulosa e/ou conexa. Nessa apresentação, mostraremos alguns resultados interessantes sobre esse problema e suas variantes.

• Data/horário: 04/03/2021 – 16hs
• Local: Online
• Palestrante: Ana Shirley F. Silva.
• Título: Grafos Temporais Eulerianos
• Resumo:  grafos temporais são grafos que mudam ao longo do tempo. Nesta apresentação, iremos estudar os vários problemas relacionados à existência de passeios e trilhas eulerianas em um grafo temporal. Provamos que quase todas as possíveis variações levam a problemas NP-completos, mesmo em casos onde o grafo considerado permanece constante ao longo do tempo. Este trabalho está sendo desenvolvido em co-autoria com Andréa Marino (Università degli Studi di Firenze).