Fomin, Fedor V. ;
Golovach, Petr ;
Panolan, Fahad ;
Saurabh, Saket
Editing to Connected fDegree Graph
Abstract
In the EDGE EDITING TO CONNECTED fDEGREE GRAPH problem we are given a graph G, an integer k and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v) and the number of edges inthe symmetric difference of E(G) and E(F), is at most k. We show that EDGE EDITING TO CONNECTED fDEGREE GRAPH is fixedparameter tractable (FPT) by providing an algorithm solving the problem on an nvertex graph in time 2^{O(k)}n^{O(1)}. Our FPT algorithm is based on a nontrivial combination of colorcoding and fast computations of representative families over direct sum matroid of lelongation of cographic matroid associated with G and uniform matroid over the set of nonedges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing problems.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2016:5737,
author = {Fedor V. Fomin and Petr Golovach and Fahad Panolan and Saket Saurabh},
title = {{Editing to Connected fDegree Graph}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {36:136:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5737},
URN = {urn:nbn:de:0030drops57370},
doi = {10.4230/LIPIcs.STACS.2016.36},
annote = {Keywords: Connected ffactor, FPT, Representative Family, Color Coding}
}
16.02.2016
Keywords: 

Connected ffactor, FPT, Representative Family, Color Coding 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

16.02.2016 