Demaine, Erik D. ;
Goodrich, Timothy D. ;
Kloster, Kyle ;
Lavallee, Brian ;
Liu, Quanquan C. ;
Sullivan, Blair D. ;
Vakilian, Ali ;
van der Poel, Andrew
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
Abstract
We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with realworld networks) while still guaranteeing approximation ratios. The idea is to edit a given graph via vertex or edgedeletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then lift the solution to apply to the original graph. We give a general characterization of when an optimization problem is amenable to this approach, and show that it includes many wellstudied graph problems, such as Independent Set, Vertex Cover, Feedback Vertex Set, Minimum Maximal Matching, Chromatic Number, (l)Dominating Set, Edge (l)Dominating Set, and Connected Dominating Set.
To enable this framework, we develop new editing algorithms that find the approximatelyfewest edits required to bring a given graph into one of a few important graph classes (in some cases these are bicriteria algorithms which simultaneously approximate both the number of editing operations and the target parameter of the family). For bounded degeneracy, we obtain an O(r log{n})approximation and a bicriteria (4,4)approximation which also extends to a smoother bicriteria tradeoff. For bounded treewidth, we obtain a bicriteria (O(log^{1.5} n), O(sqrt{log w}))approximation, and for bounded pathwidth, we obtain a bicriteria (O(log^{1.5} n), O(sqrt{log w} * log n))approximation. For treedepth 2 (related to bounded expansion), we obtain a 4approximation. We also prove complementary hardnessofapproximation results assuming P != NP: in particular, these problems are all logfactor inapproximable, except the last which is not approximable below some constant factor 2 (assuming UGC).
BibTeX  Entry
@InProceedings{demaine_et_al:LIPIcs:2019:11158,
author = {Erik D. Demaine and Timothy D. Goodrich and Kyle Kloster and Brian Lavallee and Quanquan C. Liu and Blair D. Sullivan and Ali Vakilian and Andrew van der Poel},
title = {{Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {37:137:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11158},
URN = {urn:nbn:de:0030drops111583},
doi = {10.4230/LIPIcs.ESA.2019.37},
annote = {Keywords: structural rounding, graph editing, approximation algorithms}
}
06.09.2019
Keywords: 

structural rounding, graph editing, approximation algorithms 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 