Polynomial Kernels for Strictly Chordal Edge Modification Problems
| Autor: | Dumas, Maël, Perez, Anthony, Todinca, Ioan |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Golovach, Petr A. and Zehavi, Meirav |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Parameterized complexity
Computer Science::Discrete Mathematics graph modification [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] kernelization algorithms Theory of computation ��� Parameterized complexity and exact algorithms strictly chordal graphs ComputingMilieux_MISCELLANEOUS |
| Zdroj: | 16th International Symposium on Parameterized and Exact Computation, IPEC 16th International Symposium on Parameterized and Exact Computation, IPEC, Sep 2021, Lisbonne (online), Portugal. pp.17:1--17:16 |
| Popis: | We consider the Strictly Chordal Editing problem, where one is given an undirected graph G = (V,E) and a parameter k ��� ��� and seeks to edit (add or delete) at most k edges from G to obtain a strictly chordal graph. Problems Strictly Chordal Completion and Strictly Chordal Deletion are defined similarly, by only allowing edge additions for the former, and only edge deletions for the latter. Strictly chordal graphs are a generalization of 3-leaf power graphs and a subclass of 4-leaf power graphs. They can be defined, e.g., as dart and gem-free chordal graphs. We prove the NP-completeness for all three variants of the problem and provide an O(k��) vertex-kernel for the completion version and O(k���) vertex-kernels for the two others. LIPIcs, Vol. 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), pages 17:1-17:16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|