Edge-Editing to a Dense and a Sparse Graph Class

D 2016

Edge-Editing to a Dense and a Sparse Graph Class

KOTRBČÍK, Michal, Rastislav KRÁLOVIČ and Sebastian ORDYNIAK

Basic information

Original name

Edge-Editing to a Dense and a Sparse Graph Class

Authors

KOTRBČÍK, Michal (703 Slovakia, guarantor, belonging to the institution), Rastislav KRÁLOVIČ (703 Slovakia) and Sebastian ORDYNIAK (276 Germany)

Edition

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

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/16:00094278

Organization unit

Faculty of Informatics

ISBN

978-3-662-49528-5

ISSN

DOI

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

Keywords in English

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

Abstract

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.

Citovat

KOTRBČÍK, Michal, Rastislav KRÁLOVIČ and 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, p. 562-575. ISBN 978-3-662-49528-5. Available from: https://dx.doi.org/10.1007/978-3-662-49529-2_42.

@inproceedings{1380368,
   author = {Kotrbčík, Michal and Královič, Rastislav and Ordyniak, Sebastian},
   address = {Berlin},
   booktitle = {LATIN 2016: Latin American Symposium on Theoretical Informatics},
   doi = {http://dx.doi.org/10.1007/978-3-662-49529-2_42},
   editor = {Kranakis E., Navarro G., Chávez E.},
   keywords = {Clique-editing; Degeneracy; Graph modification problems; Parameterized complexity; Treewidth},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-662-49528-5},
   pages = {562-575},
   publisher = {Springer},
   title = {Edge-Editing to a Dense and a Sparse Graph Class},
   year = {2016}
}

TY  - JOUR
ID  - 1380368
AU  - Kotrbčík, Michal - Královič, Rastislav - Ordyniak, Sebastian
PY  - 2016
TI  - Edge-Editing to a Dense and a Sparse Graph Class
PB  - Springer
CY  - Berlin
SN  - 9783662495285
KW  - Clique-editing
KW  - Degeneracy
KW  - Graph modification problems
KW  - Parameterized complexity
KW  - Treewidth
N2  - 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.
ER  -

KOTRBČÍK, Michal, Rastislav KRÁLOVIČ and Sebastian ORDYNIAK. Edge-Editing to a Dense and a Sparse Graph Class. In Kranakis E., Navarro G., Chávez E. \textit{LATIN 2016: Latin American Symposium on Theoretical Informatics}. Berlin: Springer, 2016, p.~562-575. ISBN~978-3-662-49528-5. Available from: https://dx.doi.org/10.1007/978-3-662-49529-2\_{}42.

Detailed Information on Publication Record