Edge-Editing to a Dense and a Sparse Graph Class

KOTRBČÍK, Michal, Rastislav KRÁLOVIČ a Sebastian ORDYNIAK. Edge-Editing to a Dense and a Sparse Graph Class. In Kranakis E., Navarro G., Chávez E. LATIN 2016: Latin American Symposium on Theoretical Informatics. Berlin: Springer, 2016, s. 562-575. ISBN 978-3-662-49528-5. Dostupné z: https://dx.doi.org/10.1007/978-3-662-49529-2_42.

Základní údaje

Originální název

Edge-Editing to a Dense and a Sparse Graph Class

Autoři

KOTRBČÍK, Michal (703 Slovensko, garant, domácí), Rastislav KRÁLOVIČ (703 Slovensko) a Sebastian ORDYNIAK (276 Německo)

Vydání

Berlin, LATIN 2016: Latin American Symposium on Theoretical Informatics, od s. 562-575, 14 s. 2016

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/16:00094278

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-49528-5

ISSN

DOI

http://dx.doi.org/10.1007/978-3-662-49529-2_42

Klíčová slova anglicky

Clique-editing; Degeneracy; Graph modification problems; Parameterized complexity; Treewidth

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We consider a graph edge-editing problem, where the goal is to transform a given graph G into a disjoint union of two graphs from a pair of given graph classes, investigating what properties of the classes make the problem fixed-parameter tractable. We focus on the case when the first class is dense, i.e. every such graph G has minimum degree at least |V (G)| - delta for a constant delta, and assume that the cost of editing to this class is fixed-parameter tractable parameterized by the cost. Under the assumptions that the second class either has bounded maximum degree, or is edge-monotone, can be defined in MSO2, and has bounded treewidth, we prove that the problem is fixed-parameter tractable parameterized by the cost. We also show that the problem is fixed-parameter tractable parameterized by degeneracy if the second class consists of independent sets and Subgraph Isomorphism is fixedparameter tractable for the input graphs. On the other hand, we prove that parameterization by degeneracy is in general W[1]-hard even for editing to cliques and independent sets.