2026-07-22T18:36:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5737 2024-03-06T10:36:58Z ddc:004 open_access

Editing to Connected f-Degree Graph Fomin, Fedor V. Golovach, Petr Panolan, Fahad Saurabh, Saket Connected f-factor FPT Representative Family Color Coding 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 inthe 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 2^{O(k)}n^{O(1)}. Our FPT algorithm is based on a non-trivial combination of color-coding and fast computations of representative families over direct sum matroid of l-elongation of co-graphic matroid associated with G and uniform matroid over the set of non-edges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr Golovach and Fahad Panolan and Saket Saurabh 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.36 urn:nbn:de:0030-drops-57370 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.36 eng https://creativecommons.org/licenses/by/3.0/legalcode