Header menu link for other important links
X
Editing to connected f-degree graph
F.V. Fomin, P. Golovach, , S. Saurabh
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2016
Volume: 47
   
Abstract
In the EDGE EDITING TO CONNECTED f-DEGREE 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 in E(G)ΔE(F), the symmetric difference of E(G) and E(F), is at most k. We show that EDGE EDITING TO CONNECTED f-DEGREE GRAPH is fixed-parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time 2O(k) nO(1). Our FPT algorithm is based on a non-trivial combination of colorcoding and fast computations of representative families over direct sum matroid of l-elongation of co-graphic matroid associated with G and uniform matroid over E(G)¯, the set of non-edges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing problems. © Fedor V. Fomin, Petr Golovach, Fahad Panolan, and Saket Saurabh; licensed under Creative Commons License CC-BY.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969