The theory of
 NSFPAR ID:
 10376555
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Networks
 Volume:
 76
 Issue:
 3
 ISSN:
 00283045
 Page Range / eLocation ID:
 p. 350365
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Megow, Nicole ; Smith, Adam (Ed.)Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area. We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cutbased problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes nearoptimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.more » « less

Abstract The ‐
deck of an ‐vertex graph is the multiset of subgraphs obtained from it by deleting vertices. A family of ‐vertex graphs is ‐recognizable if every graph having the same ‐deck as a graph in the family is also in the family. We prove that the family of ‐vertex graphs with no cycles is ‐recognizable when (except for ). As a consequence, the family of ‐vertex trees is ‐recognizable when and . It is known that this fails when . 
We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on
n vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at leasts . We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants 0 <A <B such that (under optimal play) Proposer wins with high probability if, while Decider wins with high probability if . This is a factor of larger than the lower bound coming from the off‐diagonal Ramsey number r (3,s ). 
In the article “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs” (Networks
39 (1) (2002), 53‐60), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using onlyO (n ) variables and constraints) and remarkably strong (defining an integral polytope). In this note, we point out that Williams' formulation, as originally stated, is incorrect. Specifically, we construct a binary feasible solution to Williams' formulation that does not represent a spanning tree. Fortunately, there is a simple fix, which is to restrict the choice of the root vertices in the primal and dual spanning trees, whereas Williams explicitly allowed them to be chosen arbitrarily. The same flaw and fix apply to a subsequent formulation of Williams (“A zero‐one programming model for contiguous land acquisition.” Geographical Analysis34 (4) (2002), 330‐349). 
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected boundeddegree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph math formula consisting of math formula edges (for a prespecified constant math formula), where the decision for different edges should be consistent with the same subgraph math formula. Can this task be performed by inspecting only a constant number of edges in G? Our main results are: We show that if every tvertex subgraph of G has expansion math formula then one can (deterministically) construct a sparse spanning subgraph math formula of G using few inspections. To this end we analyze a “local” version of a famous minimumweight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3regular graphs of high girth, in which every tvertex subgraph has expansion math formula. We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.more » « less