skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs

Fomin, Fedor V. ; Golovach, Petr A.

Algorithmica, 2021-07, Vol.83 (7), p.2170-2214 [Periódico revisado por pares]

New York: Springer US

Texto completo disponível

Citações Citado por
  • Título:
    Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs
  • Autor: Fomin, Fedor V. ; Golovach, Petr A.
  • Assuntos: Algorithm Analysis and Problem Complexity ; Algorithms ; Computer Science ; Computer Systems Organization and Communication Networks ; Data Structures and Information Theory ; Graph coloring ; Graph theory ; Graphs ; Kernels ; Mathematics of Computing ; Minimum weight ; Optimization ; Parameterization ; Polynomials ; Theory of Computation ; Vertex sets
  • É parte de: Algorithmica, 2021-07, Vol.83 (7), p.2170-2214
  • Descrição: We study algorithmic properties of the graph class C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k . It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from C H O R D A L - k e . More precisely, we identify a large class of optimization problems on C H O R D A L - k e solvable in time 2 O ( k log k ) · n O ( 1 ) . Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on C H O R D A L - k e when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of C H O R D A L - k e graphs appears to be appealing from the perspective of kernelization (with parameter k ). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on C H O R D A L - k e graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of C H O R D A L - k e , namely, I N T E R V A L - k e and S P L I T - k e graphs.
  • Editor: New York: Springer US
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.