David Eppstein - Publications

Subgraph isomorphism

Subgraph isomorphism is a very general form of pattern matching in which one attempts to find a target graph as a subgraph of a larger input graph. It is NP-complete, but it has many applications and algorithms are known for many special cases.

• Planar orientations with low out-degree and compaction of adjacency matrices.
  M. Chrobak and D. Eppstein.
  Theor. Comp. Sci. 86 (2): 243–266, 1991.

  Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. One consequence is a parallel algorithm to list all subgraphs isomorphic to \(K_3\) or \(K_4\).

• Connectivity, graph minors, and subgraph multiplicity.
  D. Eppstein.
  Tech. Rep. 92-06, ICS, UCI, 1992.
  J. Graph Th. 17: 409–416, 1993.

  It was known that planar graphs have \(O(n)\) subgraphs isomorphic to \(K_3\) or \(K_4\). That is, \(K_3\) and \(K_4\) have linear subgraph multiplicity. This paper shows that the graphs with linear subgraph multiplicity in the planar graphs are exactly the 3-connected planar graphs. Also, the graphs with linear subgraph multiplicity in the outerplanar graphs are exactly the 2-connected outerplanar graphs.

  More generally, let \(\mathcal{F}\) be a minor-closed family, and let \(x\) be the smallest number such that some complete bipartite graph \(K_{x,y}\) is a forbidden minor for \(\mathcal{F}\). Then the \(x\)-connected graphs have linear subgraph multiplicity for \(\mathcal{F}\), and there exists an \((x-1)\)-connected graph (namely \(K_{x-1,x-1}\) that does not have linear subgraph multiplicity. When \(x\le 3\) or when \(x=4\) and the minimal forbidden minors for \(\mathcal{F}\) are triangle-free, then the graphs with linear subgraph multiplicity for \(\mathcal{F}\) are exactly the \(x\)-connected graphs.

  Please refer only to the journal version, and not the earlier technical report: the technical report had a bug that was repaired in the journal version.

• Arboricity and bipartite subgraph listing algorithms.
  D. Eppstein.
  Tech. Rep. 94-11, ICS, UCI, 1994.
  Inf. Proc. Lett. 51: 207–211, 1994.

  For any sparse family of graphs, one can list in linear time all complete bipartite subgraphs of a graph in the family. There are O(n) complete bipartite subgraphs of a graph in the family, and the sum of the numbers of vertices in these subgraphs is also O(n).

  Nowadays these results can also be interpreted as a form of formal concept analysis. If a set of objects and attributes is sparse (e.g., if it is generated by adding objects and attributes one at a time, where each newly-added object is given O(1) attributes and each newly-added attribute is held by O(1) objects) then the total size of all concepts in its concept lattice is linear, and this lattice may be generated in linear time.

• Subgraph isomorphism in planar graphs and related problems.
  D. Eppstein.
  Tech. Rep. 94-25, ICS, UCI, 1994.
  6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 632–640.
  arXiv:cs.DS/9911003.
  J. Graph Algorithms and Applications 3 (3): 1–27, 1999.

  Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper, "Diameter and treewidth in minor-closed graph families", presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.

• Diameter and treewidth in minor-closed graph families.
  D. Eppstein.
  arXiv:math.CO/9907126.
  Algorithmica 27: 275–291, 2000 (special issue on treewidth, graph minors, and algorithms).

  This paper introduces the diameter-treewidth property (later known as bounded local treewidth): a functional relationship between the diameter of its graph and its treewidth. Previously known results imply that planar graphs have bounded local treewidth; we characterize the other minor-closed families with this property. Specifically, minor-closed family F has bounded local treewidth if and only if there exists an apex graph G that is not in F; an apex graph is a graph that can be made planar by removing a single vertex. The minor-free families that exclude an apex graph (and therefore have bounded local treewidth) include the bounded-genus graphs (for which, as with planar graphs, we show a linear bound for the treewidth as a function of the diameter) and K_3,a-free graphs. As a consequence, subgraph isomorphism for subgraphs of bounded size and approximations to several NP-hard optimization problems can be computed efficiently on these graphs, extending previous results for planar graphs.

  Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version. Since its publication, there have been many more works on local treewidth. The class of problems that could be solved quickly on graphs of bounded local treewidth was extended and classified by Frick and Grohe, "Deciding first-order properties of locally tree-decomposable structures", J. ACM 48: 1184–1206, 2001; the proof that bounded local treewidth is equivalent to having an excluded apex minor was simplified, and the dependence of the treewidth on diameter improved, by a subsequent paper of Demaine and Hajiaghayi, "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica 40: 211–215, 2004. The concept of local treewidth is the basis for the theory of bidimensionality, a general framework for fixed-parameter-tractable algorithms and approximation algorithms in minor-closed graph families; for a survey, see Demaine and Hajiaghayi, "The bidimensionality theory and its algorithmic applications", The Computer J. 51: 292–302, 2008.

• Confluent drawings: visualizing non-planar diagrams in a planar way.
  M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
  arXiv:cs.CG/0212046.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
  J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.

  We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.

• Approximate Topological Matching of Quadrilateral Meshes.
  D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
  Proc. IEEE Int. Conf. Shape Modeling and Applications (SMI 2008), Stony Brook, New York, pp. 83–92.
  The Visual Computer 25 (8): 771–783, 2009.

  We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.

  (Preprint)

• The h-index of a graph and its application to dynamic subgraph statistics.
  D. Eppstein and E. S. Spiro.
  arXiv:0904.3741.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada.
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 278–289.
  J. Graph Algorithms and Applications 16 (2): 543–567, 2012.

  We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.

  (Slides)

• Listing all maximal cliques in sparse graphs in near-optimal time.
  D. Eppstein, M. Löffler, and D. Strash.
  arXiv:1006.5440.
  Workshop on Exact Algorithms for NP-Hard Problems, Dagstuhl, Germany, 2010.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 403–414.
  

  We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3^d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs," which combines results from this and a different conference paper.

• Extended dynamic subgraph statistics using h-index parameterized data structures.
  D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
  Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
  Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
  arXiv:1009.0783.
  Theor. Comput. Sci. 447: 44–52, 2012 (special issue for COCOA 2010).

  An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein and D. Strash.
  10th Int. Symp. Experimental Algorithms, Crete, 2011.
  Springer, Lecture Notes in Comp. Sci. 6630, 2011, pp. 364–375.
  arXiv:1103.0318.

  We experiment with our degeneracy-based algorithm for listing maximal cliques in sparse graphs and show that it works well on large graphs drawn from several repositories of real-world social networks and bioinformatics networks.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs", which combines results from this and a different conference paper.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein, M. Löffler, and D. Strash.
  J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).

  This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.

• Planar induced subgraphs of sparse graphs.
  G. Borradaile, D. Eppstein, and P. Zhu.
  arXiv:1408.5939.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 1–12.
  J. Graph Algorithms & Applications 19 (1): 281–297, 2015.

  We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that m/5.22 vertices are sufficient and m/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.

• 2-3 cuckoo filters for faster triangle listing and set intersection.
  D. Eppstein, M. T. Goodrich, M. Mitzenmacher, and M. Torres.
  Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), Chicago, 2017, pp. 247–260.
  

  We show that bit-parallel algorithm design techniques, on a machine of word size w, can speed up the time for sparse set intersection by a factor of log w/w. The main data structure underlying our algorithms is the cuckoo filter, a variant of cuckoo hash tables that has operations similar to a Bloom filter but outperforms Bloom filters in several respects.

• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes.
  D. Eppstein, E. Havvaei, and S. Gupta.
  arXiv:2101.09918.
  Proc. 23rd International Symposium on Fundamentals of Computation Theory, 2021.
  Springer, Lecture Notes in Comp. Sci. 12867 (2021), pp. 217–229.
  

  We provide a partial classification of the complexity of parameterized graph problems of the form "find a \(k\)-vertex induced subgraph with property \(X\) in a larger subgraph with property \(Y\)", in terms of the existence of large cliques and large independent sets in the graphs with properties \(X\) and \(Y\).

• Quasipolynomiality of the smallest missing induced subgraph.
  D. Eppstein, A. Lincoln, and V. V. Williams.
  arXiv:2306.11185.
  J. Graph Algorithms & Applications 27 (5): 329–339, 2023.

  The smallest graph that is not an induced subgraph of a given graph can be found in time \(n^{O(\log n)}\). The exponent is optimal, up to constant factors, under the exponential time hypothesis.