M. Kotrbcık, R. Kralovic,S. Ordyniak:

"Edge-Editing to a Dense and a Sparse Graph Class";

Talk: Latin American Theoretical Informatics Symposium, Ensenada, Mexico; 2016-04-11 - 2016-04-15; in: "Proceedings of LATIN 2016: Theoretical Informatics - 12th Latin American Symposium", (2016), ISBN: 978-3-662-49528-5; 562 - 575.

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)| − δ for a constant δ, 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.

http://publik.tuwien.ac.at/files/publik_257506.pdf

Created from the Publication Database of the Vienna University of Technology.