@article{demaine_goodrich_kloster_lavallee_liu_sullivan_vakilian_poel_2019, title={Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}, volume={144}, ISSN={["1868-8969"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85074821909&partnerID=MN8TOARS}, DOI={10.4230/LIPIcs.ESA.2019.37}, abstractNote={We develop a new 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 real-world networks) while still guaranteeing approximation ratios. The idea is to $\textit{edit}$ a given graph via vertex- or edge-deletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then $\textit{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 well-studied graph problems, such as Independent Set, Vertex Cover, Feedback Vertex Set, Minimum Maximal Matching, Chromatic Number, ($\ell$-)Dominating Set, Edge ($\ell$-)Dominating Set, and Connected Dominating Set. 
To enable this framework, we develop new editing algorithms that find the approximately-fewest edits required to bring a given graph into one of several important graph classes (in some cases, also approximating the target parameter of the family). For bounded degeneracy, we obtain a bicriteria $(4,4)$-approximation which also extends to a smoother bicriteria trade-off. 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} \cdot \log n))$-approximation. For treedepth $2$ (also related to bounded expansion), we obtain a $4$-approximation. We also prove complementary hardness-of-approximation results assuming $\mathrm{P} \neq \mathrm{NP}$: in particular, these problems are all log-factor inapproximable, except the last which is not approximable below some constant factor ($2$ assuming UGC).}, journal={27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019)}, author={Demaine, Erik D. and Goodrich, Timothy D. and Kloster, Kyle and Lavallee, Brian and Liu, Quanquan C. and Sullivan, Blair D. and Vakilian, Ali and Poel, Andrew}, year={2019} }
 @inproceedings{chin_goodrich_o'brien_reidl_sullivan_poel_2016, title={Asymptotic analysis of equivalences and core-structures in Kronecker-style graph models}, DOI={10.1109/icdm.2016.0098}, abstractNote={Growing interest in modeling large, complexnetworks has spurred significant research into generative graphmodels. Kronecker-style models (e.g. SKG and R-MAT) are oftenused due to their scalability and ability to mimic key propertiesof real-world networks. Although a few papers theoreticallyestablish these models' behavior for specific parameters, manyclaims used to justify their use are supported only empirically. In this work, we prove several results using asymptotic analysiswhich illustrate that empirical studies may not fully capture thetrue behavior of the models. Paramount to the widespread adoption of Kronecker-stylemodels was the introduction of a linear-time edge-samplingvariant (R-MAT), which existing literature typically treats asinterchangeable with SKG. We prove that although several R-MAT formulations are asymptotically equivalent, their behaviordiverges from that of SKG. Further, we show these resultsare observable even at relatively small graph sizes. Second, weconsider a case where asymptotic analysis reveals unexpectedbehavior within a given model.}, booktitle={2016 ieee 16th international conference on data mining (icdm)}, author={Chin, A. J. and Goodrich, T. D. and O'Brien, M. P. and Reidl, F. and Sullivan, Blair D. and Poel, A.}, year={2016}, pages={829–834} }
 @article{farrell_goodrich_lemons_reidl_villaamil_sullivan_2015, title={Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs}, volume={9479}, ISBN={["978-3-319-26783-8"]}, ISSN={["1611-3349"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84951869780&partnerID=MN8TOARS}, DOI={10.1007/978-3-319-26784-5_3}, abstractNote={We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks where edges correspond to shared attributes. Specifically, we fully characterize the degeneracy of random intersection graphs, and prove that the model asymptotically almost surely produces graphs with hyperbolicity at least $$\log {n}$$ . Further, we prove that when degenerate, the graphs generated by this model belong to a bounded-expansion graph class with high probability, a property particularly suitable for the design of linear time algorithms.}, journal={ALGORITHMS AND MODELS FOR THE WEB GRAPH, (WAW 2015)}, author={Farrell, Matthew and Goodrich, Timothy D. and Lemons, Nathan and Reidl, Felix and Villaamil, Fernando Sanchez and Sullivan, Blair D.}, year={2015}, pages={29–41} }