A Polynomial Kernel for Diamond-Free Editing
| Autor: | Junjie Ye, Yixin Cao, R. B. Sandeep, Ashutosh Rai |
|---|---|
| Přispěvatelé: | Wagner, Michael |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Polynomial General Computer Science 02 engineering and technology 0102 computer and information sciences Edge (geometry) engineering.material 01 natural sciences Combinatorics Polynomial kernel Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 0101 mathematics Mathematics 000 Computer science knowledge general works Applied Mathematics 010102 general mathematics Diamond A diamond Computer Science Applications Kernel (image processing) 010201 computation theory & mathematics Computer Science Theory of computation engineering 020201 artificial intelligence & image processing Null graph |
| Zdroj: | 26th Annual European Symposium on Algorithms (ESA 2018) |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-021-00891-y |
| Popis: | An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being a 3-connected graph and the classical complexity dichotomy suggest that except for $H$ being a complete/empty graph, $H$-free editing problems admit polynomial kernels only for a few small graphs $H$. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of $H$-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink