Data: 30/07/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Co-treewidth: The Treewidth of the Complement Graph as a Parameter
Palestrante: Uéverton Souza (UFF)


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 the opposite is not valid. Problems like Longest Cycle, Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by treewidth, but they cannot be solved in FPT-time when parameterized by clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For problems that are fixed-parameter tractable concerning treewidth, but intractable for clique-width, there must still be infinite families of instances with bounded clique-width and unbounded treewidth that can be solved efficiently. Therefore, in this paper, we consider the treewidth of the complement of the graph, called co-treewidth, as a parameter. We show that Longest Cycle, Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are all FPT when parameterized by the co-treewidth. Besides, dealing with Equitable Coloring and Precoloring Extension, which are W[1]-hard for treewidth, we show that both problems are linear-time solvable on graphs with bounded co-treewidth. These results exemplify that co-treewidth is a useful width parameter for handling dense instances in problems for which an FPT algorithm for clique-width is unlikely.

This talk is based on joint work with Gabriel Duarte (Fluminense Federal University, Brazil), Mateus de Oliveira Oliveira (University of Bergen, Norway), Fahad Panolan (IIT Hyderabad, India)