Seminário de Flavia Bonomo (Departamento de Computación, FCEN, Universidad de Buenos Aires, Argentina).
Dia 12/03 (quarta-feira), 10 horas, Sala H-324B.
Transmissão pelo Canal do PESC no Youtube.

Title: List matrix partition problems on chordal graphs parameterized by leafage  

Abstract:
Graph k-coloring and k-clique cover are examples of partition problems in graphs, in the first case into k independent sets, in the second case into k cliques. Moreover, maximum clique and maximum independent set are examples of partition problems into two sets, one arbitrary and the other one required to be a clique (resp. independent set), with the addition of a linear objective function to maximize. These are examples of matrix partition problems. For each symmetric matrix M over {0,1,*}, the M-partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges joining them, or to have all edges joining them, as encoded in the matrix. Moreover, the vertices of the input graph can be equipped with lists, restricting the parts to which a vertex can be placed. Even if the first four problems (k-coloring, k-clique cover, maximum clique and maximum independent set) are polynomially solvable on chordal graphs, Feder, Hell, Klein, Nogueira and Protti in 2005 proved that there are M-partition problems (without lists) that remain NP-complete for chordal graphs. In this talk, making use of a graph width parameter called "thinness", we will show that all list matrix partition problems with linear objective functions are XP on chordal graphs, parameterized by the leafage of the chordal graph. (The leafage of a chordal graph is the minimum number of leaves in a tree such that the graph can be realized as an intersection graph of subtrees of that tree.)
These results are from joint works with Diego De Estrada and with Nick Brettell, Andrea Munaro and Daniël Paulusma.

Bio:
Flavia Bonomo é licenciada em Ciências Matemáticas e doutora em Ciências da Computação pela Universidade de Buenos Aires. Atualmente atua como Professora Associada com dedicação exclusiva no Departamento de Computação da FCEN-UBA e Pesquisadora do ICC-CONICET (Argentina). Sua principal área de pesquisa é a Teoria dos Grafos, embora também tenha artigos publicados sobre tópicos de Pesquisa Operacional, e mantém estreita colaboração nesses temas desde 2002 com pesquisadores da COPPE, UFRJ. No campo da Teoria dos Grafos seus principais tópicos de interesse cobrem as caracterizações estruturais de classes de grafos, o estudo de diferentes parâmetros de largura em grafos, e a delimitação de fronteiras em termos de complexidade computacional e classes de grafos para vários problemas de otimização combinatória.