Editing to a Planar Graph of Given Degrees

August 11, 2015 Β· Declared Dead Β· πŸ› Journal of computer and system sciences (Print)

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

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma, Dimitrios M. Thilikos arXiv ID 1508.02773 Category cs.DS: Data Structures & Algorithms Cross-listed cs.CC Citations 7 Venue Journal of computer and system sciences (Print) Last Checked 4 months ago
Abstract
We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$, a weight function $w\colon V\cup E\rightarrow \mathbb{N}$, a cost function $c\colon V\cup E\rightarrow \mathbb{N}$ and a degree function $Ξ΄\colon V\rightarrow \mathbb{N}_0$, together with three integers $k_v, k_e$ and $C$. The question is whether we can delete a set of vertices of total weight at most $k_v$ and a set of edges of total weight at most $k_e$ so that the total cost of the deleted elements is at most $C$ and every non-deleted vertex $v$ has degree $Ξ΄(v)$ in the resulting graph $G'$. We also consider the variant in which $G'$ must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by $k_v+k_e$. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by $k_v+k_e$.
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