# On Undirected Two-commodity Integral Flow, Disjoint Paths and Strict Terminal Connection Problems

Speaker: Alexsander A. de Melo, COPPE-UFRJ.

Date: 30 sep 2020, 16h.

Abstract: Even, Itai and Shamir (1976) proved simple two-commodity integral flow is NP-complete both in the directed and undirected cases. In particular, the directed case was shown to be NP-complete even if one demand is unitary, which was improved by Fortune, Hopcroft and Wyllie (1980) who proved the problem is still NP-complete if both demands are unitary. The undirected case, on the other hand, was proved by Robertson and Seymour (1995) to be polynomial-time solvable if both demands are constant. Nevertheless, the complexity of the undirected case with exactly one constant demand has remained unknown. We close this forty year complexity gap, by showing the undirected case is NP-complete even if exactly one demand is unitary. As a by-product, we obtain the NP-completeness of determining whether a graph contains 1 + d pairwise vertex-disjoint paths, such that one path is between a given pair of vertices and d paths are between a second given pair of vertices. Additionally, we investigate the complexity of another related network design problem called Strict Terminal Connection.

Obs.: This is a joint work with Celina M. H. de Figueiredo (PESC/COPPE/UFRJ) and Uéverton dos Santos Souza (IC/UFF).

# The monochromatic transversal game on clique-hypergraphs of powers of cycles

Speaker: Wilder P. Mendes, UFF.

Date: 26 aug 2020, 16h30.

Abstract: We introduce the monochromatic transversal game where the players, Alice and Bob, alternately colours vertices of a hypergraph. Alice, who colours the vertices with red, wins the game if she obtains a red transversal; and Bob wins if he does not let it happen, i.e. there exists a monochromatic blue hyperedge. Both players are enabled to start the game and they play optimally. We analyze the game played on clique-hypergraphs of complete graphs, paths, and powers of cycles. For each of these graphs, we show a strategy that allows one of the players to win the game.

Obs.: This joint work with Simone Dantas (IME/UFF), Sylvain Gravier (CNRS, Université Grenoble Alpes) and Rodrigo Marinho (IST, University of Lisbon, Portugal), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).

Support:

www.antenabrasil.uff.br

# Range-Relaxed Graceful Game

Speaker: Deise L. de Oliveira, UFF.

Date: 26 aug 2020, 16h.

Abstract: The Range-Relaxed Graceful Game is played in a simple graph G, by two players, Alice and Bob, who alternately assign a previously unused label f(v) \in £={0, ..., k}, k >=|E(G)|, to a previously unlabeled vertex v \in V(G). Alice's goal is to end up with a vertex labeling of whole G where all of its edges have distinct labels and Bob's goal is to prevent it from happening. When k=|E(G)|, it is called Graceful game. We investigate the graceful game in cartesian and corona products of graphs, and determine that Bob has a winning strategy in all investigated families independently of who starts the game. Additionally, we present the first results in the range-relaxed graceful game.

Obs.: This joint work with Simone Dantas (IME-UFF) and Atílio G. Luiz (UFC), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).

Support:

www.antenabrasil.uff.br

# Relating hypergraph parameters of generalized power graphs

Speaker: Lucas L. S. Portugal, IME-UFF.

Date: 29 jul 2020, 16h.

Abstract: Graph parameters like the chromatic number, independence number, clique number and many others alongside with their corresponding adjacency matrix have been broadly studied and extended to hypergraphs classes. A generalized power graph $G^k_s$ of a graph $G$ is $k$-uniform hypergraph constructed by blowing up each vertex of $G$ into a $s$-set of vertices and then adding $k-2s$ vertices of degree one to each edge, where $k\geq 2s$. A natural question is whether there exists any relation between structural parameters and spectral parameters of $G^k_s$ with the respective parameters of the original graph $G$. In this paper we positively answer this question and investigate the parameters behavior.

Obs.: This joint work with Renata Del Vecchio (IME/UFF) and Simone Dantas (IME/UFF), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).

Support:

www.antenabrasil.uff.br

# Recent algorithmic results on equitable coloring

Speaker: Vinicius Santos, UFMG.

Date: 18 dec 2019, 11h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: A proper coloring of a graph is a labeling of its vertex set such that adjacent vertices receive distinct labels. Many problems can be modelled using graph colorings, such as scheduling and task assignment problems. On such problems, one may be interested in the case where the coloring is balanced in the following sense: the number of times two different colors occurs in the graph can differ by at most one. Such proper colorings are called equitable colorings.

Similarly to the traditional version, determining whether a graph has an equitable coloring with a given amount of colors is a computationally hard problem. However, for many settings where coloring is tractable, the problem becomes hard for the equitable version. In this talk we present some recent advances on this problem, such as polynomial time algorithms for some special cases and positive and negative results concerning the parameterized complexity of the problem.

This is joint work with Matheus Guedes and Guilherme Gomes.

Speakers: Ignasi Sau, LIRMM; Ueverton Souza, IC-UFF.

Date: 27 nov 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Nesta palestra faremos uma breve introdução sobre algoritmos e complexidade parametrizada, uma das áreas mais promissoras da teoria da computação. Em seguida serão apresentados alguns problemas de nosso interesse particular tais como deleção de vértices em grafos com bounded treewidth para obtenção de estruturas livres de certos subgrafos induzidos. Em especial abordaremos o desenvolvimento de algoritmos de tempo single-exponencial com relação a treewidth do grafo de entrada para resolução problemas como deleção de vértices para obtenção de grafos livres de conjuntos independentes induzidos de tamanho k.

# Jogo Mapa do Tesouro

Speaker: Andressa Martins Moraes, UFRJ/PPGI/AMN.

Date: 30 sep 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário apresentarei o Jogo Mapa do Tesouro, um jogo em grafos aplicado na educação com objetivo de avaliar o desenvolvimento da aprendizagem utilizando conceitos da neurociência e empregando uma estrutura baseada em grafos.

# The size-Ramsey number of powers of bounded degree trees

Speaker: Taísa Martins, IMPA.

Date: 28 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges where in any s-colouring of E(G) there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex tree is linear on n.

This is a joint work with S. Berger, Y. Kohayakawa, G. S. Maesaka, W. Mendonça, G. O. Mota and O. Parczyk.

# Dificuldade e Eficiência de Problemas em Grafos, Strings e Permutações

Speaker: Luis Felipe Ignácio Cunha, IME-UFF.

Date: 21 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário, trataremos de problemas em grafos, strings e permutações. Estes problemas são desafiadores do ponto de vista combinatório e possuem muitas questões intrigantes há anos. Apresentaremos nosso avanços nos estudos abaixo.

-- Admissibilidade: desejamos obter num grafo G o menor inteiro t, tal que exista uma árvore geradora T cuja distância em T entre cada par de vértices vizinhos de G seja no máximo t;
-- Tesselabilidade: uma tesselação de um grafo G é uma partição do conjunto de vértices em cliques. Desejamos obter o menor t, tal que existam t tesselações cuja união das tesselações cubra o conjunto das arestas do grafo;
-- Blocos haplótipos: dadas k strings binárias, desejamos obter todas subsequências maximais cujos elementos em cada coluna sejam iguais.
-- Indexação de strings: desejamos preprocessar uma string binária de modo a responder em tempo constante se há uma substring de tamanho k com i cópias de 1s, para valores arbitrários de k e i;
-- Distância, Diâmetro, Centralidade, Mediana e Convexidade em permutações: estes são problemas associados a grupos simétricos de permutações, que possuem muitas aplicações em biologia matemática, cujo intuito é compreender melhor a filogenia de espécies.
Além de estudos obtidos nesses temas, serão apresentadas as colaborações em pesquisa e atividades de ensino e extensão em desenvolvimento.

Pagina 1 de 2