Source author record

Glencora Borradaile

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics math.CO Computational Complexity cs.CY Machine Learning math.AT

Catalog footprint

Research overview

24works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$ . Our proof implies a linear time algorithm for sampling from $\mathcal T$ . Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$ . For graphs of cutwidth $c$ , we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$ .

preprint2020arXiv

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$ , the minimum bounded chain problem: given a $d$ -dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$ -cycle $C$ in $\mathcal{K}$ , find the minimum $d$ -chain with boundary $C$ , and the minimum homologous chain problem: given a $(d+1)$ -manifold $\mathcal{M}$ and a $d$ -chain $D$ in $\mathcal{M}$ , find the minimum $d$ -chain homologous to $D$ . We show strong hardness results for both problems even for small values of $d$ ; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log β_d})$ -approximation algorithm for the minimum bounded chain problem where $β_d$ is the $d$ th Betti number of $\mathcal{K}$ . Finally, we provide an $O(\sqrt{\log n_{d+1}})$ -approximation algorithm for the minimum homologous chain problem where $n_{d+1}$ is the number of $d$ -simplices in $\mathcal{M}$ .

preprint2020arXiv

Whose Tweets are Surveilled for the Police: An Audit of Social-Media Monitoring Tool via Log Files

Social media monitoring by law enforcement is becoming commonplace, but little is known about what software packages for it do. Through public records requests, we obtained log files from the Corvallis (Oregon) Police Department's use of social media monitoring software called DigitalStakeout. These log files include the results of proprietary searches by DigitalStakeout that were running over a period of 13 months and include 7240 social media posts. In this paper, we focus on the Tweets logged in this data and consider the racial and ethnic identity (through manual coding) of the users that are therein flagged by DigitalStakeout. We observe differences in the demographics of the users whose Tweets are flagged by DigitalStakeout compared to the demographics of the Twitter users in the region, however, our sample size is too small to determine significance. Further, the demographics of the Twitter users in the region do not seem to reflect that of the residents of the region, with an apparent higher representation of Black and Hispanic people. We also reconstruct the keywords related to a Narcotics report set up by DigitalStakeout for the Corvallis Police Department and find that these keywords flag Tweets unrelated to narcotics or flag Tweets related to marijuana, a drug that is legal for recreational use in Oregon. Almost all of the keywords have a common meaning unrelated to narcotics (e.g.\ broken, snow, hop, high) that call into question the utility that such a keyword based search could have to law enforcement.

preprint2016arXiv

A PTAS for Three-Edge Connectivity in Planar Graphs

We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement $r \in \{0,1,2,3\}$ for every vertex, we seek the minimum-weight subgraph that contains, for every pair of vertices $u$ and $v$ , at least $\min\{ r(v), r(u)\}$ edge-disjoint $u$ -to- $v$ paths. We give a polynomial-time approximation scheme (PTAS) for this problem when the input graph is planar and the subgraph may use multiple copies of any given edge. This generalizes an earlier result for $r \in \{0,1,2\}$ . In order to achieve this PTAS, we prove some properties of triconnected planar graphs that may be of independent interest.

preprint2016arXiv

Minimum cycle and homology bases of surface embedded graphs

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the $1$ -dimensional ( $\mathbb{Z}_2$ )-homology classes) of an undirected graph embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the $1$ -skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic $O(n^ω+2^{2g}n^2+m)$ -time algorithm for graphs embedded on an orientable surface of genus $g$ . The best known existing algorithms for surface embedded graphs are those for general graphs: an $O(m^ω)$ time Monte Carlo algorithm and a deterministic $O(nm^2/\log n + n^2 m)$ time algorithm. For the minimum homology basis problem, we give a deterministic $O((g+b)^3 n \log n + m)$ -time algorithm for graphs embedded on an orientable or non-orientable surface of genus $g$ with $b$ boundary components, assuming shortest paths are unique, improving on existing algorithms for many values of $g$ and $n$ . The assumption of unique shortest paths can be avoided with high probability using randomization or deterministically by increasing the running time of the homology basis algorithm by a factor of $O(\log n)$ .

preprint2015arXiv

Optimal dynamic program for r-domination problems over tree decompositions

There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems are optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to $r$ -domination problems. In $r$ -dominating set, one wished to find a minimum subset $S$ of vertices such that every vertex of $G$ is within $r$ hops of some vertex in $S$ . In connected $r$ -dominating set, one additionally requires that the set induces a connected subgraph of $G$ . We give a $O((2r+1)^{\mathrm{tw}} n)$ time algorithm for $r$ -dominating set and a $O((2r+2)^{\mathrm{tw}} n^{O(1)})$ time algorithm for connected $r$ -dominating set in $n$ -vertex graphs of treewidth $\mathrm{tw}$ . We show that the running time dependence on $r$ and $\mathrm{tw}$ is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.

preprint2015arXiv

Planar Induced Subgraphs of Sparse Graphs

We show that every graph has an induced pseudoforest of at least $n-m/4.5$ vertices, an induced partial 2-tree of at least $n-m/5$ vertices, and an induced planar subgraph of at least $n-m/5.2174$ vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest $K_h$ -minor-free graph in a given graph can sometimes be at most $n-m/6+o(m)$ .

preprint2015arXiv

The two-edge connectivity survivable-network design problem in planar graphs

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement) r(v) in {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min{r(u), r(v)} edge-disjoint u-to-v paths for every pair u, v of vertices. We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O(n log n). Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.

preprint2015arXiv

Towards single face shortest vertex-disjoint paths in undirected planar graphs

Given $k$ pairs of terminals $\{(s_{1}, t_{1}), \ldots, (s_{k}, t_{k})\}$ in a graph $G$ , the min-sum $k$ vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ldots, Q_{k}\}$ of vertex-disjoint paths with minimum total length, where $Q_{i}$ is an $s_i$ -to- $t_i$ path between $s_i$ and $t_i$ . We consider the problem in planar graphs, where little is known about computational tractability, even in restricted cases. Kobayashi and Sommer propose a polynomial-time algorithm for $k \le 3$ in undirected planar graphs assuming all terminals are adjacent to at most two faces. Colin de Verdiere and Schrijver give a polynomial-time algorithm when all the sources are on the boundary of one face and all the sinks are on the boundary of another face and ask about the existence of a polynomial-time algorithm provided all terminals are on a common face. We make progress toward Colin de Verdiere and Schrijver's open question by giving an $O(kn^5)$ time algorithm for undirected planar graphs when $\{(s_{1}, t_{1}), \ldots, (s_{k}, t_{k})\}$ are in counter-clockwise order on a common face.

preprint2014arXiv

A polynomial-time approximation scheme for Euclidean Steiner forest

We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed eps > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + eps)-approximation to the minimum-length forest that connects every requested pair of terminals.

preprint2014arXiv

Covering nearly surface-embedded graphs with a fixed number of balls

A recent result of Chepoi, Estellon and Vaxes [DCG '07] states that any planar graph of diameter at most 2R can be covered by a constant number of balls of size R; put another way, there are a constant-sized subset of vertices within which every other vertex is distance half the diameter. We generalize this result to graphs embedded on surfaces of fixed genus with a fixed number of apices, making progress toward the conjecture that graphs excluding a fixed minor can also be covered by a constant number of balls. To do so, we develop two tools which may be of independent interest. The first gives a bound on the density of graphs drawn on a surface of genus $g$ having a limit on the number of pairwise-crossing edges. The second bounds the size of a non-contractible cycle in terms of the Euclidean norm of the degree sequence of a graph embedded on surface.

preprint2014arXiv

Improving Robustness of Next-Hop Routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following {\sc tree augmentation} problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that {\sc tree augmentation} is NP-hard in general and present a simple $\frac{1}{2}$ -approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, {\sc tree augmentation} has not been previously studied.

preprint2014arXiv

Lower bounds for testing digraph connectivity with one-pass streaming algorithms

In this note, we show that three graph properties - strong connectivity, acyclicity, and reachability from a vertex $s$ to all vertices - each require a working memory of $Ω(εm)$ on a graph with $m$ edges to be determined correctly with probability greater than $(1+ε)/2$ .

preprint2013arXiv

Boundary-to-boundary flows in planar graphs

We give an iterative algorithm for finding the maximum flow between a set of sources and sinks that lie on the boundary of a planar graph. Our algorithm uses only O(n) queries to simple data structures, achieving an O(n log n) running time that we expect to be practical given the use of simple primitives. The only existing algorithm for this problem uses divide and conquer and, in order to achieve an O(n log n) running time, requires the use of the (complicated) linear-time shortest-paths algorithm for planar graphs.

preprint2013arXiv

Maximum st-flow in directed planar graphs via shortest paths

Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to shortest paths for the same reason - so long as the source and the sink are on a common face. In this paper, we give a correspondence between maximum flows and shortest paths via duality in directed planar graphs with no constraints on the source and sink. We believe this a promising avenue for developing algorithms that are more practical than the current asymptotically best algorithms for maximum st-flow.

preprint2013arXiv

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

For an undirected $n$ -vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$ , what is the weight of a min $st$ -cut in $G$ ? We show how to answer such queries in constant time with $O(n\log^4n)$ preprocessing time and $O(n\log n)$ space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in $O(n\log^4n)$ time and $O(n\log n)$ space. Additionally, an explicit representation can be obtained in $O(C)$ time and space where $C$ is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead, or deterministically with an additional $\log^2 n$ factor in the preprocessing times.

preprint2013arXiv

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets

We describe an algorithm that takes as input n points in the plane and a parameter ε, and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a (1 + ε)-approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has bounded sharpest angle, our algorithm's output has O(n) vertices, its weight is O(1) times the minimum spanning tree weight, and the algorithm's running time is bounded by O(n \sqrt{log log n}). We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem.

preprint2012arXiv

Batch Active Learning via Coordinated Matching

Most prior work on active learning of classifiers has focused on sequentially selecting one unlabeled example at a time to be labeled in order to reduce the overall labeling effort. In many scenarios, however, it is desirable to label an entire batch of examples at once, for example, when labels can be acquired in parallel. This motivates us to study batch active learning, which iteratively selects batches of $k>1$ examples to be labeled. We propose a novel batch active learning method that leverages the availability of high-quality and efficient sequential active-learning policies by attempting to approximate their behavior when applied for $k$ steps. Specifically, our algorithm first uses Monte-Carlo simulation to estimate the distribution of unlabeled examples selected by a sequential policy over $k$ step executions. The algorithm then attempts to select a set of $k$ examples that best matches this distribution, leading to a combinatorial optimization problem that we term "bounded coordinated matching". While we show this problem is NP-hard in general, we give an efficient greedy solution, which inherits approximation bounds from supermodular minimization theory. Our experimental results on eight benchmark datasets show that the proposed approach is highly effective

preprint2012arXiv

Connectivity Oracles for Planar Graphs

We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or "on" (recovered). We wish to answer connectivity queries with respect to the "on" subgraph. The model has two natural variants, one in which there are $d$ edge/vertex failures that precede all connectivity queries, and one in which failures/recoveries and queries are intermixed. We present a $d$ -failure connectivity oracle for planar graphs that processes any $d$ edge/vertex failures in $sort(d,n)$ time so that connectivity queries can be answered in $pred(d,n)$ time. (Here $sort$ and $pred$ are the time for integer sorting and integer predecessor search over a subset of $[n]$ of size $d$ .) Our algorithm has two discrete parts. The first is an algorithm tailored to triconnected planar graphs. It makes use of Barnette's theorem, which states that every triconnected planar graph contains a degree-3 spanning tree. The second part is a generic reduction from general (planar) graphs to triconnected (planar) graphs. Our algorithm is, moreover, provably optimal. An implication of Patrascu and Thorup's lower bound on predecessor search is that no $d$ -failure connectivity oracle (even on trees) can beat $pred(d,n)$ query time. We extend our algorithms to the subgraph connectivity model where edge/vertex failures (but no recoveries) are intermixed with connectivity queries. In triconnected planar graphs each failure and query is handled in $O(\log n)$ time (amortized), whereas in general planar graphs both bounds become $O(\log^2 n)$ .

preprint2011arXiv

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

We give an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

preprint2011arXiv

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. The schemes run in O(n log n) time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu from planar graphs to bounded-genus graphs: any future problems shown to admit the required structure theorem for planar graphs will similarly extend to bounded-genus graphs.

preprint2011arXiv

The Knapsack Problem with Neighbour Constraints

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.

preprint2010arXiv

Multiple source, single sink maximum flow in a planar graph

We give an $O(n^{1.5}\log n)$ time algorithm for finding the maximum flow in a directed planar graph with multiple sources and a single sink. The techniques generalize to a subquadratic time algorithm for bounded genus graphs.

preprint2010arXiv

Randomly removing g handles at once

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g-1$ with constant distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere with $g$ handles attached, Indyk and Sidiropoulos' method gives an embedding into a distribution over planar graphs with distortion $2^{O(g)}$ , by iteratively removing the handles. By removing all $g$ handles at once, we present a probabilistic embedding with distortion $O(g^2)$ for both orientable and non-orientable graphs. Our result is obtained by showing that the nimum-cut graph of Erickson and Har Peled (2004) has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma of Lee and Sidiropoulos (2009).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Glencora Borradaile

Research overview

Is this your work?

24 publications

Low-stretch spanning trees of graphs with bounded width

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

Whose Tweets are Surveilled for the Police: An Audit of Social-Media Monitoring Tool via Log Files

A PTAS for Three-Edge Connectivity in Planar Graphs

Minimum cycle and homology bases of surface embedded graphs

Optimal dynamic program for r-domination problems over tree decompositions

Planar Induced Subgraphs of Sparse Graphs

The two-edge connectivity survivable-network design problem in planar graphs

Towards single face shortest vertex-disjoint paths in undirected planar graphs

A polynomial-time approximation scheme for Euclidean Steiner forest

Covering nearly surface-embedded graphs with a fixed number of balls

Improving Robustness of Next-Hop Routing

Lower bounds for testing digraph connectivity with one-pass streaming algorithms

Boundary-to-boundary flows in planar graphs

Maximum st-flow in directed planar graphs via shortest paths

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets

Batch Active Learning via Coordinated Matching

Connectivity Oracles for Planar Graphs

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

The Knapsack Problem with Neighbour Constraints

Multiple source, single sink maximum flow in a planar graph

Randomly removing g handles at once

See the researcher in context

Building this map preview