text: Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems. Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in O (m^ 2 3 ) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^0.94). The new data structure is also simpler. Geometric connectivity asks to maintain a dynamic set of n geometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, O (n^ 2 3 ), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries, such as arbitrary 2D line segments, d-dimensional simplices, and d-dimensional balls.
  @cite_35: 
  @cite_26: 
  @cite_22: 
  @cite_28: Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. To find an almost minimum circuit an @math algorithm is presented. A direct algorithm for finding a minimum circuit has an @math behavior. It is refined to yield an @math average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are given. The first has an @math worst case bound ( @math for planar graphs); the second takes @math time on the average; the third has an @math worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with @math average behavior.
  @cite_1: This paper presents an efficient fully dynamic graph algorithm for maintaining the transitive closure of a directed graph. The algorithm updates the adjacency matrix of the transitive closure with each update to the graph; hence, each reachability query of the form "Is there a directed path from i to j?" can be answered in O(1) time. The algorithm is randomized and has a one-sided error; it is correct when answering yes, but has O(1 nc) probability of error when answering no, for any constant c. In acyclic graphs, worst case update time is O(n2). In general graphs, the update time is O(n2.26). The space complexity of the algorithm is O(n2).
  @cite_32: (MATH) Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph @math and a subset of vertices @math , to support insertions and deletions in @math and connectivity queries (are two vertices connected @?) in the subgraph induced by @math . We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using an elegant combination of several simple ideas. Our method requires linear space, @math amortized update time, and @math query time, where @math is the matrix multiplication exponent and @math hides polylogarithmic factors.
  @cite_3: We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the graph in question, and not on the number of vertices. The bounds obtained improve upon various previously known results.
  @cite_6: We present several new algorithms for detecting short fixed length cycles in digraphs. The new algorithms utilize fast rectangular matrix multiplication algorithms together with a dynamic programming approach similar to the one used in the solution of the classical chain matrix product problem. The new algorithms are instantiations of a generic algorithm that we present for finding a directed C k , i.e., a directed cycle of length k, in a digraph, for any fixed k ≥ 3. This algorithm partitions the prospective C k 's in the input digraph G = (V,E) into O(logk V) classes, according to the degrees of their vertices. For each cycle class we determine, in O(Eck log V) time, whether G contains a C k from that class, where c k = c k (ω) is a constant that depends only on !, the exponent of square matrix multiplication. The search for cycles from a given class is guided by the solution of a small dynamic programming problem. The total running time of the obtained deterministic algorithm is therefore O(Eck logk+1 V).For C 3 , we get c 3 = 2ω (ω + 1) 4 we get c 4 = (4ω - 1) (2ω + 1) 5 we get c 5 = 3ω (ω + 2) k for k ≥ 6 is a difficult task. We conjecture that c k = (k + 1)ω (2ω + k - 1), for every odd k. The values of c k for even k ≥ 6 seem to exhibit a much more complicated dependence on ω.
summary: For more difficult dynamic graph problems, the goal is typically changed from getting polylogarithmic bounds to finding better exponents in polynomial bounds; for example, see all the papers on directed reachability @cite_1 @cite_26 @cite_35 @cite_22 . Evidence suggests that dynamic subgraph connectivity fits this category. It was observed @cite_32 that finding triangles (3-cycles) or quadrilaterals (4-cycles) in directed graphs can be reduced to @math vertex updates. Thus, an update bound better than @math appears unlikely without FMM, since the best running time for finding triangles without FMM is @math , dating back to STOC'77 @cite_28 . Even with FMM, known results are only slightly better: finding triangles and quadrilaterals takes time @math @cite_3 and @math @cite_6 respectively. Thus, current knowledge prevents an update bound better than @math .