Biologia molecular e genética (parte II)

Speaker: Felipe R. Silva, EMBRAPA/UNICAMP.

Date: 17 aug 2021, 16h30.

Place: Google Meet: kkd-ktkr-swg.

 

Biologia molecular e genética

Speaker: Felipe R. Silva, EMBRAPA/UNICAMP.

Date: 12 aug 2021, 16h.

Place: Google Meet: kkd-ktkr-swg.

Abstract: TBA.

 

Co-degeneracy and co-treewidth: Using the complement to solve dense instances

Speaker: Gabriel Lagoa Duarte, U, UFF.

Date: 28 jul 2021, 14h.

Place: Google Meet: swt-uoda-eyn.

Abstract: Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies bounded clique-width, but not vice versa. Problems like Longest Cycle,Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by the treewidth, but they cannot be solved in FPT time when parameterized by the clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For a given problem that is fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently.

In this work, we initiate a systematic study of the parameters co-treewidth (the treewidth of the complement of the input graph) and co-degeneracy (the degeneracy of the complement of the input graph). We show that Longest Cycle,Longest Path, and Edge Dominating Setare FPT when parameterized by co-degeneracy. On the other hand, Graph Coloringis para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open the complexity of the problem parameterized by co-degeneracy.

Additionally, we show that Precoloring Extensionis fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth. These results give evidence that co-treewidth is a useful width parameter for handling dense instances of problems for which an FPT algorithm for clique-width is unlikely to exist. Finally, we develop an algorithmic framework for co-degeneracy based on the notion of Bondy-Chvátal closure.

This is joint work with Mateus de Oliveira Oliveira and Uéverton S. Souza.

 

Reducing graph transversals via edge contractions

Speaker: Vinícius Fernandes dos Santos, UFMG.

Date: 30 jun 2021, 14h.

Place: Google Meet: meet.google.com/npz-qztp-riw.

Abstract: For a graph parameter $\pi$, the Contraction($\pi$) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which $\pi$ has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $\pi$ is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection H according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in H, which in particular imply that Contraction($\pi$) is co-NP-hard even for fixed k=d=1 when $\pi$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $\pi$ is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Joint work with Paloma T. Lima, Ignasi Sau and Uéverton S. Souza, available at arXiv:2005.01460.

 

Maximum cut and Steiner tree restricted to interval graphs and related families

Speaker: Celina de Figueiredo, COPPE UFRJ.

Date: 12 mai 2021, 14h.

Place: Google Meet: meet.google.com/nhe-vccv-qrf

Abstract: We consider Column 16 -- Graph Restrictions and Their Effect -- of D. S. Johnson's Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns, and several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We focus on columns MaxCut and StTree, where there are recent resolved entries for interval graphs and related families.

 

Colorações restritas de grafos aleatórios

Speakers: Guilherme Mota, USP.

Date: 28 apr 2021, 14h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: Dados grafos G, H_1 e H_2, denote por G ---> (H_1, H_2) a seguinte propriedade: em toda coloração das arestas de G há uma cópia monocromática de H_1 ou uma cópia "arco-íris" de H_2 (uma cópia de H_2 em que todas as arestas têm cores diferentes).

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. Neste seminário vou determinar o "threshold" para a propriedade G (n, p) ---> (H_1, H_2) quando H_2 é uma floresta.

Este é um trabalho conjunto com Maurício Collares, Yoshiharu Kohayakawa e Carlos Gustavo Moreira.

 

Grupo de Thompson da Basílica

Speakers: Miguel Del Rio (doutor UNICAMP, 2019).

Date: 24 mar 2021, 16h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: O grupo de Thompson da Basílica, um grupo introduzido por Belk e Forrest em [2] e que tem relação com os grupos de Thompson F, T, V e muitos outros grupos com definições análogas a estes.

Nós estudaremos o problema da conjugação no grupo de Thompson da Basílica. Para isso vamos examinar a solução desse problema no grupo de Thompson T. Nossa solução usa uma técnica similar a aquela usada por Belk e Matucci em [3] com a vantagem de que achamos que pode ser usada em outros grupos como os grupos de rearranjos estudados por Belk e Forrest em [2].

[1] J. Belk and B. Forrest. A Thompson Group for the Basilica. Groups, Geometry, and Dynamics 9.4 (2015): 975–1000. doi:10.4171/GGD/333.

[2] J. Belk and B. Forrest. Rearrangement Groups of Fractals. Preprint (2015). arXiv:1510.03133.

[3] J. Belk and F. Matucci. Conjugacy and Dynamics in Thompson's Groups. Geometriae Dedicata 169.1 (2014): 239–261.

 

Propagação da COVID-19 usando medidas de centralidade de grafos

Speaker: Átila Arueira Jones, Inst. Federal do Sudeste de Minas Gerais.

Date: 02 dec 2020, 16h.

Place: Google Meet: meet.google.com/gbn-pvqf-bpw.

Abstract: Atualmente há uma grande preocupação na disseminação do vírus causador da doença COVID-19 e o distanciamento social ainda é a forma mais indicada para conter a propagação da doença. Neste trabalho modelamos a relação de alunos e professores de uma instituição de ensino através de um grafo para então simular a difusão do vírus, segundo o modelo epidêmico SIR. A propagação da epidemia foi observada tomando diferentes situações iniciais, a partir de um único vértice infectado inicial, de acordo com medidas de centralidade calculadas. Então observamos a influência dessas medidas na difusão do vírus e como isso está relacionado ao tempo do pico da epidemia.

Obs.: Trabalho em conjunto com Priscila R. Almeida (professora IFsudMG) e Luísa Gonçalves (graduando Engenharia Mecatrônica - IFsudMG).

 

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.

Place: Google Meet: meet.google.com/ost-kzem-mqk.

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).

 

Pagina 1 de 3