A polynomial kernel for $3$-leaf power deletion

November 11, 2019 Β· Declared Dead Β· πŸ› Algorithmica

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Jungho Ahn, Eduard Eiben, O-joung Kwon, Sang-il Oum arXiv ID 1911.04249 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM, math.CO Citations 6 Venue Algorithmica Last Checked 4 months ago
Abstract
For a non-negative integer $\ell$, the $\ell$-leaf power of a tree $T$ is a simple graph $G$ on the leaves of $T$ such that two vertices are adjacent in $G$ if and only if their distance in $T$ is at most $\ell$. We provide a polynomial kernel for the problem of deciding whether we can delete at most $k$ vertices to make an input graph a $3$-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ for the problem to output an equivalent instance $(G',k')$ such that $k'\leq k$ and $G'$ has at most $O(k^{14})$ vertices.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted