@article{jain_mizutani_sullivan_2022, title={Faster Decomposition ofWeighted Graphs into Cliques using Fisher's Inequality}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85133019615&partnerID=MN8TOARS}, DOI={10.48550/arXiv.2206.07286}, abstractNote={Mining groups of genes that consistently co-express is an important problem in biomedical research, where it is critical for applications such as drug-repositioning and designing new disease treatments. Recently, Cooley et al. modeled this problem as Exact Weighted Clique Decomposition (EWCD) in which, given an edge-weighted graph $G$ and a positive integer $k$, the goal is to decompose $G$ into at most $k$ (overlapping) weighted cliques so that an edge's weight is exactly equal to the sum of weights for cliques it participates in. They show EWCD is fixed-parameter-tractable, giving a $4^k$-kernel alongside a backtracking algorithm (together called cricca) to iteratively build a decomposition. Unfortunately, because of inherent exponential growth in the space of potential solutions, cricca is typically able to decompose graphs only when $k \leq 11$. In this work, we establish reduction rules that exponentially decrease the size of the kernel (from $4^k$ to $k2^k$) for EWCD. In addition, we use insights about the structure of potential solutions to give new search rules that speed up the decomposition algorithm. At the core of our techniques is a result from combinatorial design theory called Fisher's inequality characterizing set systems with restricted intersections. We deploy our kernelization and decomposition algorithms (together called DeCAF) on a corpus of biologically-inspired data and obtain over two orders of magnitude speed-up over cricca. As a result, DeCAF scales to instances with $k \geq 17$.}, journal={arXiv}, author={Jain, S. and Mizutani, Y. and Sullivan, B.}, year={2022} }
 @article{fraser_lavallee_sullivan_2022, title={Gerrymandering Trees: Parameterized Hardness}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85130804743&partnerID=MN8TOARS}, DOI={10.48550/arXiv.2205.06857}, abstractNote={In a representative democracy, the electoral process involves partitioning geographical space into districts which each elect a single representative. These representatives craft and vote on legislation, incentivizing political parties to win as many districts as possible (ideally a plurality). Gerrymandering is the process by which district boundaries are manipulated to the advantage of a desired candidate or party. We study the parameterized complexity of Gerrymandering, a graph problem (as opposed to Euclidean space) formalized by Cohen-Zemach et al. (AAMAS 2018) and Ito et al. (AAMAS 2019) where districts partition vertices into connected subgraphs. We prove that Unit Weight Gerrymandering is W[2]-hard on trees (even when the depth is two) with respect to the number of districts $k$. Moreover, we show that Unit Weight Gerrymandering remains W[2]-hard in trees with $\ell$ leaves with respect to the combined parameter $k+\ell$. In contrast, Gupta et al. (SAGT 2021) give an FPT algorithm for Gerrymandering on paths with respect to $k$. To complement our results and fill this gap, we provide an algorithm to solve Gerrymandering that is FPT in $k$ when $\ell$ is a fixed constant.}, journal={arXiv}, author={Fraser, A. and Lavallee, B. and Sullivan, B.D.}, year={2022} }
 @article{mizutani_sullivan_2022, title={Improved Parameterized Complexity of Happy Set Problems}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85134643405&partnerID=MN8TOARS}, DOI={10.48550/arXiv.2207.06623}, abstractNote={We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Maximum Edge Happy Set (MaxEHS)--also known as Densest k-Subgraph. Given a graph $G$ and an integer $k$, MaxHS asks for a set $S$ of $k$ vertices such that the number of $\textit{happy vertices}$ with respect to $S$ is maximized, where a vertex $v$ is happy if $v$ and all its neighbors are in $S$. We show that MaxHS can be solved in time $\mathcal{O}\left(2^\textsf{mw} \cdot \textsf{mw} \cdot k^2 \cdot |V(G)|\right)$ and $\mathcal{O}\left(8^\textsf{cw} \cdot k^2 \cdot |V(G)|\right)$, where $\textsf{mw}$ and $\textsf{cw}$ denote the $\textit{modular-width}$ and the $\textit{clique-width}$ of $G$, respectively. This resolves the open questions posed in literature. The MaxEHS problem is an edge-variant of MaxHS, where we maximize the number of $\textit{happy edges}$, the edges whose endpoints are in $S$. In this paper we show that MaxEHS can be solved in time $f(\textsf{nd})\cdot|V(G)|^{\mathcal{O}(1)}$ and $\mathcal{O}\left(2^{\textsf{cd}}\cdot k^2 \cdot |V(G)|\right)$, where $\textsf{nd}$ and $\textsf{cd}$ denote the $\textit{neighborhood diversity}$ and the $\textit{cluster deletion number}$ of $G$, respectively, and $f$ is some computable function. This result implies that MaxEHS is also fixed-parameter tractable by $\textit{twin cover number}$.}, journal={arXiv}, author={Mizutani, Y. and Sullivan, B.D.}, year={2022} }
 @article{drange_dregi_lokshtanov_sullivan_2022, title={On the threshold of intractability}, volume={124}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85116011132&partnerID=MN8TOARS}, DOI={10.1016/j.jcss.2021.09.003}, abstractNote={The computational complexity of the graph modification problems Threshold Editing and Chain Editing has been an important open question in computational graph theory for more than 15 years. These problems consist of adding and deleting the fewest possible edges to transform a graph into a threshold or chain graph. We show that both problems are NP-hard, resolving a conjecture by Natanzon, Shamir, and Sharan from 2001. On the positive side, we show both problems admit quadratic vertex kernels and give subexponential time parameterized algorithms solving both problems in 2O(klog⁡k)+nO(1) time. Few natural problems are known to be in this complexity class. These results also extend to the completion and deletion variants of both problems, and threshold/chain graphs are the only known graph classes for which all three versions—completion, deletion, and editing—are both NP-complete and solvable in subexponential parameterized time.}, journal={Journal of Computer and System Sciences}, author={Drange, P.G. and Dregi, M.F. and Lokshtanov, D. and Sullivan, B.D.}, year={2022}, pages={1–25} }
 @article{goodrich_horton_sullivan_2021, title={An Updated Experimental Evaluation of Graph Bipartization Methods}, volume={26}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85119170953&partnerID=MN8TOARS}, DOI={10.1145/3467968}, abstractNote={We experimentally evaluate the practical state-of-the-art in graph bipartization (Odd Cycle Transversal (OCT)), motivated by the need for good algorithms for embedding problems into near-term quantum computing hardware. We assemble a preprocessing suite of fast input reduction routines from the OCT and Vertex Cover (VC) literature and compare algorithm implementations using Quadratic Unconstrained Binary Optimization problems from the quantum literature. We also generate a corpus of frustrated cluster loop graphs, which have previously been used to benchmark quantum annealing hardware. The diversity of these graphs leads to harder OCT instances than in existing benchmarks.}, journal={ACM Journal of Experimental Algorithmics}, author={Goodrich, T.D. and Horton, E. and Sullivan, B.D.}, year={2021} }
 @article{breen-mckay_lavallee_sullivan_2021, title={Hardness of the Generalized Coloring Numbers}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85121786987&partnerID=MN8TOARS}, journal={arXiv}, author={Breen-McKay, M. and Lavallee, B. and Sullivan, B.D.}, year={2021} }
 @inproceedings{cooley_greene_issac_pividori_sullivan_2021, title={Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition}, url={http://dx.doi.org/10.1137/1.9781611976830.11}, DOI={10.1137/1.9781611976830.11}, abstractNote={We present a new combinatorial model for identifying regulatory modules in gene co-expression data using a decomposition into weighted cliques. To capture complex interaction effects, we generalize the previously-studied weighted edge clique partition problem. As a first step, we restrict ourselves to the noise-free setting, and show that the problem is fixed parameter tractable when parameterized by the number of modules (cliques). We present two new algorithms for finding these decompositions, using linear programming and integer partitioning to determine the clique weights. Further, we implement these algorithms in Python and test them on a biologically-inspired synthetic corpus generated using real-world data from transcription factors and a latent variable analysis of co-expression in varying cell types.}, booktitle={SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21)}, publisher={Society for Industrial and Applied Mathematics}, author={Cooley, Madison and Greene, Casey S. and Issac, Davis and Pividori, Milton and Sullivan, Blair D.}, year={2021}, month={Jan}, pages={111–122} }
 @article{cooley_greene_issac_pividori_sullivan_2021, title={Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85108789587&partnerID=MN8TOARS}, journal={arXiv}, author={Cooley, M. and Greene, C.S. and Issac, D. and Pividori, M. and Sullivan, B.D.}, year={2021} }
 @article{kun_michael p. o'brien_pilipczuk_sullivan_2021, title={Polynomial Treedepth Bounds in Linear Colorings}, volume={83}, ISSN={["1432-0541"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85090215196&partnerID=MN8TOARS}, DOI={10.1007/s00453-020-00760-0}, abstractNote={Abstract}, number={1}, journal={ALGORITHMICA}, author={Kun, Jeremy and Michael P. O'Brien and Pilipczuk, Marcin and Sullivan, Blair D.}, year={2021}, month={Jan}, pages={361–386} }
 @article{pividori_lu_li_su_johnson_wei_feng_namjou_kiryluk_kullo_et al._2021, title={Projecting genetic associations through gene expression patterns highlights disease etiology and drug mechanisms}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85115761345&partnerID=MN8TOARS}, DOI={10.1101/2021.07.05.450786}, abstractNote={Abstract}, journal={bioRxiv}, author={Pividori, M. and Lu, S. and Li, B. and Su, C. and Johnson, M.E. and Wei, W.-Q. and Feng, Q. and Namjou, B. and Kiryluk, K. and Kullo, I. and et al.}, year={2021} }
 @inbook{du_ferrari_heitsch_hurley_mennicke_sullivan_xu_2021, title={Secondary Structure Ensemble Analysis via Community Detection}, volume={22}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85101125344&partnerID=MN8TOARS}, DOI={10.1007/978-3-030-57129-0_4}, abstractNote={We explored the extent to which graph algorithms for community detection can improve the mining of structural information from the predicted Boltzmann/Gibbs ensemble for the biological objects known as RNA secondary structures. As described, a new computational pipeline was developed, implemented, and tested against the prior method RNAStructProfiling. Since the new approach was judged to provide more structural information in 75% of the test cases, this proof-of-principle analysis supports efforts to improve the data mining of RNA secondary structure ensembles.}, booktitle={Association for Women in Mathematics Series}, author={Du, H. and Ferrari, M.M. and Heitsch, C. and Hurley, F. and Mennicke, C.V. and Sullivan, B.D. and Xu, B.}, year={2021}, pages={55–81} }
 @article{mizutani_staker_sullivan_2021, title={Sparse dominating sets and balanced neighborhood partitioning}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85121833484&partnerID=MN8TOARS}, journal={arXiv}, author={Mizutani, Y. and Staker, A. and Sullivan, B.D.}, year={2021} }
 @article{reidl_sullivan_2020, title={A color-avoiding approach to subgraph counting in bounded expansion classes}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85095561220&partnerID=MN8TOARS}, journal={arXiv}, author={Reidl, F. and Sullivan, B.D.}, year={2020} }
 @inproceedings{lavallee_russell_sullivan_poel_2020, title={Approximating vertex cover using structural rounding}, volume={2020-January}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85079379022&partnerID=MN8TOARS}, DOI={10.1137/1.9781611976007.6}, abstractNote={In this work, we provide the first practical evaluation of the structural rounding framework for approximation algorithms. Structural rounding works by first editing to a well-structured class, efficiently solving the edited instance, and "lifting" the partial solution to recover an approximation on the input. We focus on the well-studied Vertex Cover problem, and edit to the class of bipartite graphs (where Vertex Cover has an exact polynomial time algorithm). In addition to the naive lifting strategy for Vertex Cover described by Demaine et al., we introduce a suite of new lifting strategies and measure their effectiveness on a large corpus of synthetic graphs. We find that in this setting, structural rounding significantly outperforms standard 2-approximations. Further, simpler lifting strategies are extremely competitive with the more sophisticated approaches. The implementations are available as an open-source Python package, and all experiments are replicable.}, booktitle={Proceedings of the Workshop on Algorithm Engineering and Experiments}, author={Lavallee, B. and Russell, H. and Sullivan, B.D. and Poel, A.}, year={2020}, pages={70–80} }
 @article{brown_moritz_michael p. o'brien_reidl_reiter_sullivan_2020, title={Exploring neighborhoods in large metagenome assembly graphs using spacegraphcats reveals hidden sequence diversity}, volume={21}, ISSN={["1474-760X"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85087661224&partnerID=MN8TOARS}, DOI={10.1186/s13059-020-02066-4}, abstractNote={Abstract}, number={1}, journal={GENOME BIOLOGY}, author={Brown, C. Titus and Moritz, Dominik and Michael P. O'Brien and Reidl, Felix and Reiter, Taylor and Sullivan, Blair D.}, year={2020}, month={Jul} }
 @article{lavallee_russell_sullivan_poel_2019, title={Approximating vertex cover using structural rounding}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094768942&partnerID=MN8TOARS}, journal={arXiv}, author={Lavallee, B. and Russell, H. and Sullivan, B.D. and Poel, A.}, year={2019} }
 @article{sullivan_poel_woodlief_2019, title={Faster Biclique Mining in Near-Bipartite Graphs}, volume={11544}, ISBN={["978-3-030-34028-5"]}, ISSN={["1611-3349"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85076404739&partnerID=MN8TOARS}, DOI={10.1007/978-3-030-34029-2_28}, abstractNote={Identifying dense bipartite subgraphs is a common graph data mining task. Many applications focus on the enumeration of all maximal bicliques (MBs), though sometimes the stricter variant of maximal induced bicliques (MIBs) is of interest. Recent work of Kloster et al. introduced a MIB-enumeration approach designed for “near-bipartite” graphs, where the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartite graph. Their algorithm was shown to outperform the previously best known algorithm even when k was logarithmic in |V|. In this paper, we introduce two new algorithms optimized for near-bipartite graphs - one which enumerates MIBs in time $$O(M_I |V| |E| k)$$, and another based on the approach of Alexe et al. which enumerates MBs in time $$O(M_B |V| |E| k)$$, where $$M_I$$ and $$M_B$$ denote the number of MIBs and MBs in the graph, respectively. We implement all of our algorithms in open-source C++ code and experimentally verify that the OCT-based approaches are faster in practice than the previously existing algorithms on graphs with a wide variety of sizes, densities, and OCT decompositions.}, journal={ANALYSIS OF EXPERIMENTAL ALGORITHMS, SEA2 2019}, author={Sullivan, Blair D. and Poel, Andrew and Woodlief, Trey}, year={2019}, pages={424–453} }
 @inproceedings{kloster_poel_sullivan_2019, title={Mining maximal induced bicliques using odd cycle transversals}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85066094908&partnerID=MN8TOARS}, DOI={10.1137/1.9781611975673.37}, abstractNote={Many common graph data mining tasks take the form of identifying dense subgraphs (e.g. clustering, clique-finding, etc). In biological applications, the natural model for these dense substructures is often a complete bipartite graph (biclique), and the problem requires enumerating all maximal bicliques (instead of just identifying the largest or densest). The best known algorithm in general graphs is due to Dias et al., and runs in time O(M |V|^4 ), where M is the number of maximal induced bicliques (MIBs) in the graph. When the graph being searched is itself bipartite, Zhang et al. give a faster algorithm where the time per MIB depends on the number of edges in the graph. In this work, we present a new algorithm for enumerating MIBs in general graphs, whose run time depends on how "close to bipartite" the input is. Specifically, the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartite graph. Our algorithm runs in time O(M |V||E|k^2 3^(k/3) ), which is an improvement on Dias et al. whenever k <= 3log_3(|V|). We implement our algorithm alongside a variant of Dias et al.'s in open-source C++ code, and experimentally verify that the OCT-based approach is faster in practice on graphs with a wide variety of sizes, densities, and OCT decompositions.}, booktitle={SIAM International Conference on Data Mining, SDM 2019}, author={Kloster, K. and Poel, A. and Sullivan, B.D.}, year={2019}, pages={324–332} }
 @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} }
 @article{demaine_reidl_rossmanith_villaamil_sikdar_sullivan_2019, title={Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs}, volume={105}, url={https://doi.org/10.1016/j.jcss.2019.05.004}, DOI={10.1016/j.jcss.2019.05.004}, abstractNote={This research establishes that many real-world networks exhibit bounded expansion2, a strong notion of structural sparsity, and demonstrates that it can be leveraged to design efficient algorithms for network analysis. Specifically, we give a new linear-time fpt algorithm for motif counting and linear time algorithms to compute localized variants of several centrality measures. To establish structural sparsity in real-world networks, we analyze several common network models regarding their structural sparsity. We show that, with high probability, (1) graphs sampled with a prescribed sparse degree sequence; (2) perturbed bounded-degree graphs; (3) stochastic block models with small probabilities; result in graphs of bounded expansion. In contrast, we show that the Kleinberg and the Barabási–Albert model have unbounded expansion. We support our findings with empirical measurements on a corpus of real-world networks.}, journal={Journal of Computer and System Sciences}, publisher={Elsevier BV}, author={Demaine, Erik D. and Reidl, Felix and Rossmanith, Peter and Villaamil, Fernando Sánchez and Sikdar, Somnath and Sullivan, Blair D.}, year={2019}, month={Nov}, pages={199–241} }
 @article{horton_kloster_sullivan_2019, title={Subgraph centrality and walk-regularity}, volume={570}, url={https://doi.org/10.1016/j.laa.2019.02.005}, DOI={10.1016/j.laa.2019.02.005}, abstractNote={Matrix-based centrality measures have enjoyed significant popularity in network analysis, in no small part due to our ability to rigorously analyze their behavior as parameters vary. Recent work has considered the relationship between subgraph centrality, which is defined using the matrix exponential f(x)=exp⁡(x), and the walk structure of a network. In a walk-regular graph, the number of closed walks of each length must be the same for all nodes, implying uniform f-subgraph centralities for any f (or maximum f-walk entropy). We consider when non-walk-regular graphs can achieve maximum entropy, calling such graphs entropic. For parameterized measures, we are also interested in which values of the parameter witness this uniformity. To date, only one entropic graph has been identified, with only two witnessing parameter values, raising the question of how many such graphs and parameters exist. We resolve these questions by constructing infinite families of entropic graphs, as well as a family of witnessing parameters with a limit point at zero.}, journal={Linear Algebra and its Applications}, publisher={Elsevier BV}, author={Horton, Eric and Kloster, Kyle and Sullivan, Blair D.}, year={2019}, month={Jun}, pages={225–244} }
 @inproceedings{kloster_kuinke_o?brien_reidl_villaamil_sullivan_van der poel_2018, title={A practical fpt algorithm for flow decomposition and transcript assembly}, volume={2018-January}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85041407415&partnerID=MN8TOARS}, DOI={10.1137/1.9781611975055.7}, abstractNote={The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transcript assembly. We prove the problem is in FPT when parameterized by the number of paths by giving a practical linear fpt algorithm. Further, we implement and engineer a Flow Decomposition solver based on this algorithm, and evaluate its performance on RNA-sequence data. Crucially, our solver finds exact solutions while achieving runtimes competitive with a state-of-the-art heuristic. Finally, we contextualize our design choices with two hardness results related to preprocessing and weight recovery. Specifically, $k$-Flow Decomposition does not admit polynomial kernels under standard complexity assumptions, and the related problem of assigning (known) weights to a given set of paths is NP-hard.}, booktitle={Proceedings of the Workshop on Algorithm Engineering and Experiments}, author={Kloster, K. and Kuinke, P. and O?Brien, M.P. and Reidl, F. and Villaamil, F.S. and Sullivan, B.D. and Van Der Poel, A.}, year={2018}, pages={75–86} }
 @article{goodrich_horton_sullivan_2018, title={An updated experimental evaluation of graph bipartization methods}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85104339918&partnerID=MN8TOARS}, journal={arXiv}, author={Goodrich, T.D. and Horton, E. and Sullivan, B.D.}, year={2018} }
 @article{dumitrescu_fisher_goodrich_humble_sullivan_wright_2018, title={Benchmarking treewidth as a practical component of tensor network simulations}, volume={13}, ISSN={["1932-6203"]}, url={https://doi.org/10.1371/journal.pone.0207827}, DOI={10.1371/journal.pone.0207827}, abstractNote={Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network’s line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.}, number={12}, journal={PLOS ONE}, publisher={Public Library of Science (PLoS)}, author={Dumitrescu, Eugene F. and Fisher, Allison L. and Goodrich, Timothy D. and Humble, Travis S. and Sullivan, Blair D. and Wright, Andrew L.}, editor={Torre, Emanuele G. DallaEditor}, year={2018}, month={Dec} }
 @article{dumitrescu_fisher_goodrich_humble_sullivan_wrigh_2018, title={Benchmarking treewidth as a practical component of tensor-network–based quantum simulation}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85095245427&partnerID=MN8TOARS}, journal={arXiv}, author={Dumitrescu, E.F. and Fisher, A.L. and Goodrich, T.D. and Humble, T.S. and Sullivan, B.D. and Wrigh, A.L.}, year={2018} }
 @article{brown_moritz_o’brien_reidl_reiter_sullivan_2018, title={Exploring neighborhoods in large metagenome assembly graphs reveals hidden sequence diversity}, volume={11}, url={https://doi.org/10.1101/462788}, DOI={10.1101/462788}, abstractNote={Genomes computationally inferred from large metagenomic data sets are often incomplete and may be missing functionally important content and strain variation. We introduce an information retrieval system for large metagenomic data sets that exploits the sparsity of DNA assembly graphs to efficiently extract subgraphs surrounding an inferred genome. We apply this system to recover missing content from genome bins and show that substantial genomic sequence variation is present in a real metagenome. Our software implementation is available athttps://github.com/spacegraphcats/spacegraphcats under the 3-Clause BSD License.}, journal={bioRxiv}, publisher={Cold Spring Harbor Laboratory}, author={Brown, C. Titus and Moritz, Dominik and O’Brien, Michael P. and Reidl, Felix and Reiter, Taylor and Sullivan, Blair D.}, year={2018}, month={Nov} }
 @article{kloster_sullivan_van der poel_2018, title={Mining maximal induced bicliques using odd cycle transversals}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85093320378&partnerID=MN8TOARS}, journal={arXiv}, author={Kloster, K. and Sullivan, B.D. and Van Der Poel, A.}, year={2018} }
 @article{goodrich_sullivan_humble_2018, title={Optimizing adiabatic quantum program compilation using a graph-theoretic framework}, volume={17}, ISSN={1570-0755 1573-1332}, url={http://dx.doi.org/10.1007/S11128-018-1863-4}, DOI={10.1007/S11128-018-1863-4}, abstractNote={Adiabatic quantum computing has evolved in recent years from a theoretical field into an immensely practical area, a change partially sparked by D-Wave System’s quantum annealing hardware. These multimillion-dollar quantum annealers offer the potential to solve optimization problems millions of times faster than classical heuristics, prompting researchers at Google, NASA and Lockheed Martin to study how these computers can be applied to complex real-world problems such as NASA rover missions. Unfortunately, compiling (embedding) an optimization problem into the annealing hardware is itself a difficult optimization problem and a major bottleneck currently preventing widespread adoption. Additionally, while finding a single embedding is difficult, no generalized method is known for tuning embeddings to use minimal hardware resources. To address these barriers, we introduce a graph-theoretic framework for developing structured embedding algorithms. Using this framework, we introduce a biclique virtual hardware layer to provide a simplified interface to the physical hardware. Additionally, we exploit bipartite structure in quantum programs using odd cycle transversal (OCT) decompositions. By coupling an OCT-based embedding algorithm with new, generalized reduction methods, we develop a new baseline for embedding a wide range of optimization problems into fault-free D-Wave annealing hardware. To encourage the reuse and extension of these techniques, we provide an implementation of the framework and embedding algorithms.}, number={5}, journal={Quantum Information Processing}, publisher={Springer Science and Business Media LLC}, author={Goodrich, Timothy D. and Sullivan, Blair D. and Humble, Travis S.}, year={2018}, month={Apr} }
 @article{kun_o’brien_pilipczuk_sullivan_2018, title={Polynomial treedepth bounds in linear colorings}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85092833264&partnerID=MN8TOARS}, journal={arXiv}, author={Kun, J. and O’Brien, M.P. and Pilipczuk, M. and Sullivan, B.D.}, year={2018} }
 @article{demaine_goodrich_kloster_lavallee_liu_sullivan_vakilian_poel_2018, title={Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094277709&partnerID=MN8TOARS}, journal={arXiv}, author={Demaine, E.D. and Goodrich, T.D. and Kloster, K. and Lavallee, B. and Liu, Q.C. and Sullivan, B.D. and Vakilian, A. and Poel, A.}, year={2018} }
 @article{horton_kloster_sullivan_2018, title={Subgraph centrality and walk-regularity}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85093754399&partnerID=MN8TOARS}, journal={arXiv}, author={Horton, E. and Kloster, K. and Sullivan, B.D.}, year={2018} }
 @inbook{kun_o’brien_sullivan_2018, title={Treedepth Bounds in Linear Colorings}, volume={11159 LNCS}, ISBN={9783030002558 9783030002565}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-030-00256-5_27}, DOI={10.1007/978-3-030-00256-5_27}, abstractNote={Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of $$k<p$$ colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. A simple analysis of this treedepth bound shows it cannot exceed $$2^k$$ , but no graph class is known to have treedepth more than 2k. We establish polynomial upper bounds via constructive coloring algorithms in trees and intervals graphs, and conjecture that a polynomial relationship is in fact the worst case in general graphs. We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice.}, booktitle={Graph-Theoretic Concepts in Computer Science}, publisher={Springer International Publishing}, author={Kun, Jeremy and O’Brien, Michael P. and Sullivan, Blair D.}, year={2018}, pages={331–343} }
 @article{kloster_král'_sullivan_2018, title={Walk entropy and walk-regularity}, volume={546}, url={https://doi.org/10.1016/j.laa.2018.02.009}, DOI={10.1016/j.laa.2018.02.009}, abstractNote={A graph is said to be walk-regular if, for each ℓ≥1, every vertex is contained in the same number of closed walks of length ℓ. We construct a 24-vertex graph H4 that is not walk-regular yet has maximized walk entropy, SV(H4,β)=log⁡24, for some β>0. This graph is a counterexample to a conjecture of Benzi (2014) [1, Conjecture 3.1]. We also show that there exist infinitely many temperatures β0>0 so that SV(G,β0)=log⁡nG if and only if a graph G is walk-regular.}, journal={Linear Algebra and its Applications}, publisher={Elsevier BV}, author={Kloster, Kyle and Král', Daniel and Sullivan, Blair D.}, year={2018}, month={Jun}, pages={115–121} }
 @inproceedings{sullivan_van der poel_2017, title={A fast parameterized algorithm for Co-Path Set}, volume={63}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85014712605&partnerID=MN8TOARS}, DOI={10.4230/LIPIcs.IPEC.2016.28}, abstractNote={The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.}, booktitle={Leibniz International Proceedings in Informatics, LIPIcs}, author={Sullivan, B.D. and Van Der Poel, A.}, year={2017} }
 @article{kloster_kuinke_o’brien_reidl_villaamil_sullivan_van der poel_2017, title={A practical fpt algorithm for flow decomposition and transcript assembly}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094353595&partnerID=MN8TOARS}, journal={arXiv}, author={Kloster, K. and Kuinke, P. and O’Brien, M.P. and Reidl, F. and Villaamil, F.S. and Sullivan, B.D. and Van Der Poel, A.}, year={2017} }
 @article{o’brien_sullivan_2017, title={An experimental evaluation of a bounded expansion algorithmic pipeline}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85092949285&partnerID=MN8TOARS}, journal={arXiv}, author={O’Brien, M.P. and Sullivan, B.D.}, year={2017} }
 @inproceedings{asymptotic analysis of equivalences and core-structures in kronecker-style graph models_2017, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85014525949&partnerID=MN8TOARS}, DOI={10.1109/ICDM.2016.81}, booktitle={Proceedings - IEEE International Conference on Data Mining, ICDM}, year={2017}, pages={829–834} }
 @inproceedings{muzi_o’brien_reidl_sullivan_2017, title={Being even slightly shallow makes life hard}, volume={83}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85038445465&partnerID=MN8TOARS}, DOI={10.4230/LIPIcs.MFCS.2017.79}, abstractNote={We study the computational complexity of identifying dense substructures, namely $r/2$-shallow topological minors and $r$-subdivisions. Of particular interest is the case when $r=1$, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. 
In the following, we provide a negative answer: Dense $r/2$-Shallow Topological Minor and Dense $r$-Subdivsion are already NP-hard for $r = 1$ in very sparse graphs. Further, they do not admit algorithms with running time $2^{o(\mathbf{tw}^2)} n^{O(1)}$ when parameterized by the treewidth of the input graph for $r \geq 2$ unless ETH fails.}, booktitle={Leibniz International Proceedings in Informatics, LIPIcs}, author={Muzi, I. and O’Brien, M.P. and Reidl, F. and Sullivan, B.D.}, year={2017} }
 @article{muzi_o’brien_reidl_sullivan_2017, title={Being even slightly shallow makes life hard}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094429786&partnerID=MN8TOARS}, journal={arXiv}, author={Muzi, I. and O’Brien, M.P. and Reidl, F. and Sullivan, B.D.}, year={2017} }
 @article{goodrich_sullivan_humble_2017, title={Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85095056109&partnerID=MN8TOARS}, journal={arXiv}, author={Goodrich, T.D. and Sullivan, B.D. and Humble, T.S.}, year={2017} }
 @article{kloster_král_sullivan_2017, title={Walk entropy and walk-regularity}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094268676&partnerID=MN8TOARS}, journal={arXiv}, author={Kloster, K. and Král, D. and Sullivan, B.D.}, year={2017} }
 @article{bridges_collins_ferragut_laska_sullivan_2016, title={A multi-level anomaly detection algorithm for time-varying graph data with interactive visualization}, volume={6}, ISSN={1869-5450 1869-5469}, url={http://dx.doi.org/10.1007/S13278-016-0409-Y}, DOI={10.1007/S13278-016-0409-Y}, abstractNote={This work presents a modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in streaming graph data. Our goal is to detect changes at multiple levels of granularity, thereby identifying specific nodes and subgraphs causing a graph to appear anomalously. In particular, the framework detects changes in community membership, density, and node degree in a sequence of graphs where these are relatively stable. In route to this end, we introduce a new graph model, a generalization of the BTER model of Seshadhri et al., by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. This technique provides insight into a graph’s structure and internal context that may shed light on a detected event. Additionally, this multi-scale analysis facilitates intuitive visualizations by allowing users to narrow focus from an anomalous graph to particular subgraphs or nodes causing the anomaly. For evaluation, two hierarchical anomaly detectors are tested against a baseline Gaussian method on a series of sampled graphs. We demonstrate that our graph statistics-based approach outperforms both a distribution-based detector and the baseline in a labeled setting with community structure, and it accurately detects anomalies in synthetic and real-world datasets at the node, subgraph, and graph levels. To illustrate the accessibility of information made possible via this technique, the anomaly detector and an associated interactive visualization tool are tested on NCAA football data, where teams and conferences that moved within the league are identified with perfect recall, and precision >0.786.}, number={1}, journal={Social Network Analysis and Mining}, publisher={Springer Science and Business Media LLC}, author={Bridges, Robert A. and Collins, John and Ferragut, Erik M. and Laska, Jason and Sullivan, Blair D.}, year={2016}, month={Oct} }
 @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{adcock_sullivan_mahoney_2016, title={Tree decompositions and social graphs}, volume={12}, ISSN={["1944-9488"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84978531731&partnerID=MN8TOARS}, DOI={10.1080/15427951.2016.1182952}, abstractNote={Abstract Recent work has established that large informatics graphs such as social and information networks have non-trivial tree-like structure when viewed at moderate size scales. Here, we present results from the first detailed empirical evaluation of the use of tree decomposition (TD) heuristics for structure identification and extraction in social graphs. Although TDs have historically been used in structural graph theory and scientific computing, we show that—even with existing TD heuristics developed for those very different areas—TD methods can identify interesting structure in a wide range of realistic informatics graphs. Our main contributions are the following: we show that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; we show that the peripheral bags of these TDs correlate well with low-conductance communities (when they exist) found using local spectral computations; and we show that several types of large-scale “ground-truth” communities, defined by demographic metadata on the nodes of the network, are well-localized in the large-scale and/or peripheral structures of the TDs. Our other main contributions are the following: we provide detailed empirical results for TD heuristics on toy and synthetic networks to establish a baseline to understand better the behavior of the heuristics on more complex real-world networks; and we prove a theorem providing formal justification for the intuition that the only two impediments to low-distortion hyperbolic embedding are high tree-width and long geodesic cycles. Our results suggest future directions for improved TD heuristics that are more appropriate for realistic social graphs.}, number={5}, journal={INTERNET MATHEMATICS}, author={Adcock, Aaron B. and Sullivan, Blair D. and Mahoney, Michael W.}, year={2016}, pages={315–361} }
 @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} }
 @article{bridges_collins_ferragut_laska_sullivan_2015, title={Multi-Level Anomaly Detection on Time-Varying Graph Data}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84962580244&partnerID=MN8TOARS}, DOI={10.1145/2808797.2809406}, abstractNote={This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labeled, streaming graph data. We introduce a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. Specifically, probability models describing coarse subgraphs are built by aggregating node probabilities, and these related hierarchical models simultaneously detect deviations from expectation. This technique provides insight into the graphs' structure and helps contextualized detected event. For evaluation, two new hierarchical detectors are tested against a baseline Gaussian method on a synthetic graph sequence with seeded anomalies. We demonstrate that in a labeled setting with community structure, our graph statistics-based approach outperforms both a distribution-based detector and the baseline, accurately detecting anomalies at the node, subgraph, and graph levels.}, journal={PROCEEDINGS OF THE 2015 IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM 2015)}, author={Bridges, Robert A. and Collins, John P. and Ferragut, Erik M. and Laska, Jason A. and Sullivan, Blair D.}, year={2015}, pages={579–583} }
 @article{drange_dregi_lokshtanov_sullivan_2015, title={On the Threshold of Intractability}, volume={9294}, ISBN={["978-3-662-48349-7"]}, ISSN={["1611-3349"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84945584240&partnerID=MN8TOARS}, DOI={10.1007/978-3-662-48350-3_35}, abstractNote={We study the computational complexity of the graph modification problems and , adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, we show that both problems are -hard, resolving a conjecture by Natanzon, Shamir, and Sharan (2001). On the positive side, we show that these problems admit quadratic vertex kernels. Furthermore, we give a subexponential time parameterized algorithm solving in time, making it one of relatively few natural problems in this complexity class on general graphs. These results are of broader interest to the field of social network analysis, where recent work of Brandes (2014) posits that the minimum edit distance to a threshold graph gives a good measure of consistency for node centralities. Finally, we show that all our positive results extend to , as well as the completion and deletion variants of both problems.}, journal={ALGORITHMS - ESA 2015}, author={Drange, Pal Gronas and Dregi, Markus Sortland and Lokshtanov, Daniel and Sullivan, Blair D.}, year={2015}, pages={411–423} }
 @article{zig-zag numberlink is np-complete_2015, volume={23}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84929412116&partnerID=MN8TOARS}, DOI={10.2197/ipsjjip.23.239}, abstractNote={When can $t$ terminal pairs in an $m \times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the ``cover all vertices'' constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle \emph{Numberlink}; our problem is another common form of Numberlink, sometimes called \emph{Zig-Zag Numberlink} and popularized by the smartphone app \emph{Flow Free}.}, number={3}, journal={Journal of Information Processing}, year={2015}, pages={239–245} }
 @article{humble_mccaskey_bennink_billings_dazevedo_sullivan_klymko_seddiqi_2014, title={An integrated programming and development environment for adiabatic quantum optimization}, volume={7}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84920520607&partnerID=MN8TOARS}, DOI={10.1088/1749-4680/7/1/015006}, abstractNote={Adiabatic quantum computing is a promising route to the computational power afforded by quantum information processing. The recent availability of adiabatic hardware has raised challenging questions about how to evaluate adiabatic quantum optimization (AQO) programs. Processor behavior depends on multiple steps to synthesize an adiabatic quantum program, which are each highly tunable. We present an integrated programming and development environment for AQO called Jade Adiabatic Development Environment (JADE) that provides control over all the steps taken during program synthesis. JADE captures the workflow needed to rigorously specify the AQO algorithm while allowing a variety of problem types, programming techniques, and processor configurations. We have also integrated JADE with a quantum simulation engine that enables program profiling using numerical calculation. The computational engine supports plug-ins for simulation methodologies tailored to various metrics and computing resources. We present the design, integration, and deployment of JADE and discuss its potential use for benchmarking AQO programs by the quantum computer science community.}, number={1}, journal={Computational Science and Discovery}, author={Humble, T.S. and McCaskey, A.J. and Bennink, R.S. and Billings, J.J. and Dazevedo, E.D. and Sullivan, B.D. and Klymko, C.F. and Seddiqi, H.}, year={2014} }
 @inproceedings{obrien_sullivan_2014, title={Locally Estimating Core Numbers}, volume={2015-January}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84936947120&partnerID=MN8TOARS}, DOI={10.1109/ICDM.2014.136}, abstractNote={Graphs are a powerful way to model interactions and relationships in data from a wide variety of application domains. In this setting, entities represented by vertices at the 'center' of the graph are often more important than those associated with vertices on the 'fringes'. For example, central nodes tend to be more critical in the spread of information or disease and play an important role in clustering/community formation. Identifying such 'core' vertices has recently received additional attention in the context of network experiments, which analyze the response when a random subset of vertices are exposed to a treatment (e.g. Inoculation, free product samples, etc). Specifically, the likelihood of having many central vertices in any exposure subset can have a significant impact on the experiment. We focus on using k-cores and core numbers to measure the extent to which a vertex is central in a graph. Existing algorithms for computing the core number of a vertex require the entire graph as input, an unrealistic scenario in many real world applications. Moreover, in the context of network experiments, the sub graph induced by the treated vertices is only known in a probabilistic sense. We introduce a new method for estimating the core number based only on the properties of the graph within a region of radius δ around the vertex, and prove an asymptotic error bound of our estimator on random graphs. Further, we empirically validate the accuracy of our estimator for small values of δ on a representative corpus of real data sets. Finally, we evaluate the impact of improved local estimation on an open problem in network experimentation posed by Ugander et al.}, number={January}, booktitle={Proceedings - IEEE International Conference on Data Mining, ICDM}, author={Obrien, M.P. and Sullivan, B.D.}, year={2014}, pages={460–469} }
 @article{klymko_sullivan_humble_2013, title={Adiabatic quantum programming: minor embedding with hard faults}, volume={13}, ISSN={1570-0755 1573-1332}, url={http://dx.doi.org/10.1007/S11128-013-0683-9}, DOI={10.1007/s11128-013-0683-9}, abstractNote={Adiabatic quantum programming defines the time-dependent mapping of a quantum algorithm into an underlying hardware or logical fabric. An essential step is embedding problem-specific information into the quantum logical fabric. We present algorithms for embedding arbitrary instances of the adiabatic quantum optimization algorithm into a square lattice of specialized unit cells. These methods extend with fabric growth while scaling linearly in time and quadratically in footprint. We also provide methods for handling hard faults in the logical fabric without invoking approximations to the original problem and illustrate their versatility through numerical studies of embeddability versus fault rates in square lattices of complete bipartite unit cells. The studies show that these algorithms are more resilient to faulty fabrics than naive embedding approaches, a feature which should prove useful in benchmarking the adiabatic quantum optimization algorithm on existing faulty hardware.}, number={3}, journal={Quantum Information Processing}, publisher={Springer Science and Business Media LLC}, author={Klymko, Christine and Sullivan, Blair D. and Humble, Travis S.}, year={2013}, month={Nov}, pages={709–729} }
 @inbook{adcock_sullivan_hernandez_mahoney_2013, title={Evaluating OpenMP Tasking at Scale for the Computation of Graph Hyperbolicity}, volume={8122 LNCS}, ISBN={9783642406973 9783642406980}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-40698-0_6}, DOI={10.1007/978-3-642-40698-0_6}, abstractNote={We describe using OpenMP to compute δ-hyperbolicity, a quantity of interest in social and information network analysis, at a scale that uses up to 1000 threads. By considering both OpenMP workshare and tasking models to parallelize the computations, we find that multiple task levels permits finer grained tasks at runtime and results in better performance at scale than worksharing constructs. We also characterize effects of task inflation, load balancing, and scheduling overhead in this application, using both GNU and Intel compilers. Finally, we show how OpenMP 3.1 tasking clauses can be used to mitigate overheads at scale.}, booktitle={OpenMP in the Era of Low Power Devices and Accelerators}, publisher={Springer Berlin Heidelberg}, author={Adcock, Aaron B. and Sullivan, Blair D. and Hernandez, Oscar R. and Mahoney, Michael W.}, year={2013}, pages={71–83} }
 @article{sullivan_2013, title={On a conjecture of Andrica and Tomescu}, volume={16}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84880061040&partnerID=MN8TOARS}, number={3}, journal={Journal of Integer Sequences}, author={Sullivan, B.D.}, year={2013} }
 @inproceedings{sullivan_weerapurage_groer_2013, title={Parallel algorithms for graph optimization using tree decompositions}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84899764118&partnerID=MN8TOARS}, DOI={10.1109/IPDPSW.2013.242}, abstractNote={Although many NP-hard graph optimization problems can be solved in polynomial time on graphs of bounded tree-width, the adoption of these techniques into mainstream scientific computation has been limited due to the high memory requirements of the dynamic programming tables and excessive runtimes of sequential implementations. This work addresses both challenges by proposing a set of new parallel algorithms for all steps of a tree decomposition-based approach to solve the maximum weighted independent set problem. A hybrid OpenMP/MPI implementation includes a highly scalable parallel dynamic programming algorithm leveraging the MADNESS task based runtime, and computational results demonstrate scaling. This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.}, booktitle={Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013}, author={Sullivan, B.D. and Weerapurage, D. and Groer, C.}, year={2013}, pages={1838–1847} }
 @inproceedings{adcock_sullivan_mahoney_2013, title={Tree-Like Structure in Large Social and Information Networks}, url={http://dx.doi.org/10.1109/icdm.2013.77}, DOI={10.1109/icdm.2013.77}, abstractNote={Although large social and information networks are often thought of as having hierarchical or tree-like structure, this assumption is rarely tested. We have performed a detailed empirical analysis of the tree-like properties of realistic informatics graphs using two very different notions of tree-likeness: Gromov's d-hyperbolicity, which is a notion from geometric group theory that measures how tree-like a graph is in terms of its metric structure, and tree decompositions, tools from structural graph theory which measure how tree-like a graph is in terms of its cut structure. Although realistic informatics graphs often do not have meaningful tree-like structure when viewed with respect to the simplest and most popular metrics, e.g., the value of d or the tree width, we conclude that many such graphs do have meaningful tree-like structure when viewed with respect to more refined metrics, e.g., a size-resolved notion of d or a closer analysis of the tree decompositions. We also show that, although these two rigorous notions of tree-likeness capture very different tree-like structures in worst-case, for realistic informatics graphs they empirically identify surprisingly similar structure. We interpret this tree-like structure in terms of the recently-characterized "nested core-periphery" property of large informatics graphs, and we show that the fast and scalable k-core heuristic can be used to identify this tree-like structure.}, booktitle={2013 IEEE 13th International Conference on Data Mining}, publisher={IEEE}, author={Adcock, Aaron B. and Sullivan, Blair D. and Mahoney, Michael W.}, year={2013}, month={Dec}, pages={1–10} }
 @article{groër_sullivan_poole_2011, title={A mathematical analysis of the R-MAT random graph generator}, volume={58}, ISSN={0028-3045}, url={http://dx.doi.org/10.1002/net.20417}, DOI={10.1002/net.20417}, abstractNote={Abstract}, number={3}, journal={Networks}, publisher={Wiley}, author={Groër, Chris and Sullivan, Blair D. and Poole, Steve}, year={2011}, month={Apr}, pages={159–170} }
 @article{seymour_sullivan_2010, title={Counting paths in digraphs}, volume={31}, ISSN={0195-6698}, url={http://dx.doi.org/10.1016/j.ejc.2009.05.008}, DOI={10.1016/j.ejc.2009.05.008}, abstractNote={Say a digraph is k-free if it has no directed cycles of length at most k, for positive integers k. Thomasse conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on n vertices is at most (n-1)n(n+1)/15. We present an unpublished result of Bondy proving that there are at most 2n^3/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n^3/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n^4/75 using Bondy's result for Thomasse's conjecture.}, number={3}, journal={European Journal of Combinatorics}, publisher={Elsevier BV}, author={Seymour, Paul and Sullivan, Blair D.}, year={2010}, month={Apr}, pages={961–975} }
 @article{chudnovsky_seymour_sullivan_2008, title={Cycles in dense digraphs}, volume={28}, ISSN={0209-9683 1439-6912}, url={http://dx.doi.org/10.1007/S00493-008-2331-Z}, DOI={10.1007/S00493-008-2331-Z}, number={1}, journal={Combinatorica}, publisher={Springer Science and Business Media LLC}, author={Chudnovsky, Maria and Seymour, Paul and Sullivan, Blair}, year={2008}, month={Jan}, pages={1–18} }