Idioma:

Polynomial Kernel for Interval Vertex Deletion

Agrawal, Akanksha ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Zehavi, Meirav

ACM transactions on algorithms, 2023-04, Vol.19 (2), p.1-68, Article 11 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Polynomial Kernel for Interval Vertex Deletion
Autor: Agrawal, Akanksha ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Zehavi, Meirav
Assuntos: Parameterized complexity and exact algorithms ; Theory of computation
É parte de: ACM transactions on algorithms, 2023-04, Vol.19 (2), p.1-68, Article 11
Descrição: Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S⊆ V(G) of size at most k such that G-S is an interval graph. This problem is known to be NP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10k nO(1). The existence of a polynomial kernel for IVD remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative.
Editor: New York, NY: ACM
Idioma: Inglês

Voltar para lista de resultados