Implicit graph

In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function.

Neighborhood representations

The notion of an implicit graph is common in various search algorithms which are described in terms of graphs. In this context, an implicit graph may be defined as a set of rules to define all neighbors for any specified vertex. ^[1] This type of implicit graph representation is analogous to an adjacency list, in that it provides easy access to the neighbors of each vertex. For instance, in searching for a solution to a puzzle such as Rubik's Cube, one may define an implicit graph in which each vertex represents one of the possible states of the cube, and each edge represents a move from one state to another. It is straightforward to generate the neighbors of any vertex by trying all possible moves in the puzzle and determining the states reached by each of these moves; however, an implicit representation is necessary, as the state space of Rubik's Cube is too large to allow an algorithm to list all of its states. ^[2]

In computational complexity theory, several complexity classes have been defined in connection with implicit graphs, defined as above by a rule or algorithm for listing the neighbors of a vertex. For instance, PPA is the class of problems in which one is given as input an undirected implicit graph (in which vertices are n-bit binary strings, with a polynomial time algorithm for listing the neighbors of any vertex) and a vertex of odd degree in the graph, and must find a second vertex of odd degree. By the handshaking lemma, such a vertex exists; finding one is a problem in NP, but the problems that can be defined in this way may not necessarily be NP-complete, as it is unknown whether PPA = NP. PPAD is an analogous class defined on implicit directed graphs that has attracted attention in algorithmic game theory because it contains the problem of computing a Nash equilibrium. ^[3] The problem of testing reachability of one vertex to another in an implicit graph may also be used to characterize space-bounded nondeterministic complexity classes including NL (the class of problems that may be characterized by reachability in implicit directed graphs whose vertices are O(log n)-bit bitstrings), SL (the analogous class for undirected graphs), and PSPACE (the class of problems that may be characterized by reachability in implicit graphs with polynomial-length bitstrings). In this complexity-theoretic context, the vertices of an implicit graph may represent the states of a nondeterministic Turing machine, and the edges may represent possible state transitions, but implicit graphs may also be used to represent many other types of combinatorial structure. ^[4] PLS, another complexity class, captures the complexity of finding local optima in an implicit graph. ^[5]

Implicit graph models have also been used as a form of relativization in order to prove separations between complexity classes that are stronger than the known separations for non-relativized models. For instance, Childs et al. used neighborhood representations of implicit graphs to define a graph traversal problem that can be solved in polynomial time on a quantum computer but that requires exponential time to solve on any classical computer. ^[6]

Adjacency labeling schemes

In the context of efficient representations of graphs, J. H. Muller defined a local structure or adjacency labeling scheme for a graph G in a given family F of graphs to be an assignment of an O(log n)-bit identifier to each vertex of G, together with an algorithm (that may depend on F but is independent of the individual graph G) that takes as input two vertex identifiers and determines whether or not they are the endpoints of an edge in G. That is, this type of implicit representation is analogous to an adjacency matrix: it is straightforward to check whether two vertices are adjacent but finding the neighbors of any vertex may involve looping through all vertices and testing which ones are neighbors. ^[7]

Graph families with adjacency labeling schemes include:

Bounded degree graphs

If every vertex in G has at most d neighbors, one may number the vertices of G from 1 to n and let the identifier for a vertex be the (d + 1)-tuple of its own number and the numbers of its neighbors. Two vertices are adjacent when the first numbers in their identifiers appear later in the other vertex's identifier. More generally, the same approach can be used to provide an implicit representation for graphs with bounded arboricity or bounded degeneracy, including the planar graphs and the graphs in any minor-closed graph family. ^{[8] [9]}

Intersection graphs

An interval graph is the intersection graph of a set of line segments in the real line. It may be given an adjacency labeling scheme in which the points that are endpoints of line segments are numbered from 1 to 2n and each vertex of the graph is represented by the numbers of the two endpoints of its corresponding interval. With this representation, one may check whether two vertices are adjacent by comparing the numbers that represent them and verifying that these numbers define overlapping intervals. The same approach works for other geometric intersection graphs including the graphs of bounded boxicity and the circle graphs, and subfamilies of these families such as the distance-hereditary graphs and cographs. ^{[8] [10]} However, a geometric intersection graph representation does not always imply the existence of an adjacency labeling scheme, because it may require more than a logarithmic number of bits to specify each geometric object. For instance, representing a graph as a unit disk graph may require exponentially many bits for the coordinates of the disk centers. ^[11]

Low-dimensional comparability graphs

The comparability graph for a partially ordered set has a vertex for each set element and an edge between two set elements that are related by the partial order. The order dimension of a partial order is the minimum number of linear orders whose intersection is the given partial order. If a partial order has bounded order dimension, then an adjacency labeling scheme for the vertices in its comparability graph may be defined by labeling each vertex with its position in each of the defining linear orders, and determining that two vertices are adjacent if each corresponding pair of numbers in their labels has the same order relation as each other pair. In particular, this allows for an adjacency labeling scheme for the chordal comparability graphs, which come from partial orders of dimension at most four. ^{[12] [13]}

The implicit graph conjecture

Unsolved problem in mathematics:

Does every slowly-growing hereditary family of graphs have an implicit representation?

(more unsolved problems in mathematics)

Not all graph families have local structures. For some families, a simple counting argument proves that adjacency labeling schemes do not exist: only O(n log n) bits may be used to represent an entire graph, so a representation of this type can only exist when the number of n-vertex graphs in the given family F is at most 2^{O(n log n)}. Graph families that have larger numbers of graphs than this, such as the bipartite graphs or the triangle-free graphs, do not have adjacency labeling schemes. ^{[8] [10]} However, even families of graphs in which the number of graphs in the family is small might not have an adjacency labeling scheme; for instance, the family of graphs with fewer edges than vertices has 2^{O(n log n)}n-vertex graphs but does not have an adjacency labeling scheme, because one could transform any given graph into a larger graph in this family by adding a new isolated vertex for each edge, without changing its labelability. ^{[7] [10]} Kannan et al. asked whether having a forbidden subgraph characterization and having at most 2^{O(n log n)}n-vertex graphs are together enough to guarantee the existence of an adjacency labeling scheme; this question, which Spinrad restated as a conjecture, remains open. ^{[8] [10]} Among the families of graphs which satisfy the conditions of the conjecture and for which there is no known adjacency labeling scheme are the family of disk graphs and line segment intersection graphs.

Labeling schemes and induced universal graphs

If a graph family F has an adjacency labeling scheme, then the n-vertex graphs in F may be represented as induced subgraphs of a common induced universal graph of polynomial size, the graph consisting of all possible vertex identifiers. Conversely, if an induced universal graph of this type can be constructed, then the identities of its vertices may be used as labels in an adjacency labeling scheme. ^[8] For this application of implicit graph representations, it is important that the labels use as few bits as possible, because the number of bits in the labels translates directly into the number of vertices in the induced universal graph. Alstrup and Rauhe showed that any tree has an adjacency labeling scheme with log₂n + O(log* n) bits per label, from which it follows that any graph with arboricity k has a scheme with k log₂n + O(log* n) bits per label and a universal graph with n^k2^{O(log* n)} vertices. In particular, planar graphs have arboricity at most three, so they have universal graphs with a nearly-cubic number of vertices. ^[14] This bound was improved by Gavoille and Labourel who showed that planar graphs and minor-closed graph families have a labeling scheme with 2 log₂n + O(log log n) bits per label, and that graphs of bounded treewidth have a labeling scheme with log₂n + O(log log n) bits per label. ^[15] The bound for planar graphs was improved again by Bonamy, Gavoille, and Piliczuk who showed that planar graphs have a labelling scheme with (4/3+o(1))log₂n bits per label. ^[16] Finally Dujmović et al showed that planar graphs have a labelling scheme with (1+o(1))log₂n bits per label giving a universal graph with n^1+o(1) vertices. ^[17]

Evasiveness

The Aanderaa–Karp–Rosenberg conjecture concerns implicit graphs given as a set of labeled vertices with a black-box rule for determining whether any two vertices are adjacent. This definition differs from an adjacency labeling scheme in that the rule may be specific to a particular graph rather than being a generic rule that applies to all graphs in a family. Because of this difference, every graph has an implicit representation. For instance, the rule could be to look up the pair of vertices in a separate adjacency matrix. However, an algorithm that is given as input an implicit graph of this type must operate on it only through the implicit adjacency test, without reference to how the test is implemented.

A graph property is the question of whether a graph belongs to a given family of graphs; the answer must remain invariant under any relabeling of the vertices. In this context, the question to be determined is how many pairs of vertices must be tested for adjacency, in the worst case, before the property of interest can be determined to be true or false for a given implicit graph. Rivest and Vuillemin proved that any deterministic algorithm for any nontrivial graph property must test a quadratic number of pairs of vertices. ^[18] The full Aanderaa–Karp–Rosenberg conjecture is that any deterministic algorithm for a monotonic graph property (one that remains true if more edges are added to a graph with the property) must in some cases test every possible pair of vertices. Several cases of the conjecture have been proven to be true—for instance, it is known to be true for graphs with a prime number of vertices ^[19] —but the full conjecture remains open. Variants of the problem for randomized algorithms and quantum algorithms have also been studied.

Bender and Ron have shown that, in the same model used for the evasiveness conjecture, it is possible in only constant time to distinguish directed acyclic graphs from graphs that are very far from being acyclic. In contrast, such a fast time is not possible in neighborhood-based implicit graph models, ^[20]

See also

• Black box group, an implicit model for group-theoretic algorithms
• Matroid oracle, an implicit model for matroid algorithms

References

1. Korf, Richard E. (2008), "Linear-time disk-based implicit graph search", Journal of the ACM , 55 (6), Article 26, 40pp, doi:10.1145/1455248.1455250, MR   2477486, S2CID   13969607 .
2. Korf, Richard E. (2008), "Minimizing disk I/O in two-bit breadth-first search" (PDF), Proc. 23rd AAAI Conf. on Artificial Intelligence, pp. 317–324, The standard 3×3×3 Rubik's Cube contains 4.3252 × 10¹⁹ states, and is too large to search exhaustively.
3. Papadimitriou, Christos (1994), "On the complexity of the parity argument and other inefficient proofs of existence" (PDF), Journal of Computer and System Sciences , 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, archived from the original (PDF) on 2016-03-04, retrieved 2011-07-12
4. Immerman, Neil (1999), "Exercise 3.7 (Everything is a Graph)", Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag, p. 48, ISBN   978-0-387-98600-5 .
5. Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, arXiv: 0802.2831 , doi:10.1016/j.cosrev.2009.03.004 .
6. Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Exponential algorithmic speedup by a quantum walk", Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 59–68, arXiv: quant-ph/0209131 , doi:10.1145/780542.780552, MR   2121062, S2CID   308884 .
7. Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology.
8. Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics , 5 (4): 596–603, doi:10.1137/0405049, MR   1186827 .
9. Chrobak, Marek; Eppstein, David (1991), "Planar orientations with low out-degree and compaction of adjacency matrices" (PDF), Theoretical Computer Science , 86 (2): 243–266, doi: 10.1016/0304-3975(91)90020-3 .
10. Spinrad, Jeremy P. (2003), "2. Implicit graph representation", Efficient Graph Representations, American Mathematical Soc., pp. 17–30, ISBN   0-8218-2815-0 .
11. Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF), archived from the original (PDF) on 2012-03-16, retrieved 2011-07-12.
12. Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Cycle-free partial orders and chordal comparability graphs", Order , 8 (1): 49–61, doi:10.1007/BF00385814, MR   1129614, S2CID   120479154 .
13. Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "An implicit representation of chordal comparability graphs in linear time", Discrete Applied Mathematics, 158 (8): 869–875, doi: 10.1016/j.dam.2010.01.005 , MR   2602811 .
14. Alstrup, Stephen; Rauhe, Theis (2002), "Small induced-universal graphs and compact implicit graph representations" (PDF), Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 53–62, doi:10.1109/SFCS.2002.1181882, S2CID   1820524, archived from the original (PDF) on 2011-09-27, retrieved 2011-07-13.
15. Arnaud, Labourel; Gavoille, Cyril (2007), "Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs" (PDF), Proceedings of the 15th annual European Symposium on Algorithms, pp. 582–593, doi:10.1007/978-3-540-75520-3_52 .
16. Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Shorter Labeling Schemes for Planar Graphs", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 446–462, arXiv: 1908.03341 , doi:10.1007/978-3-540-75520-3_52 .
17. Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Adjacency Labelling for Planar Graphs (and Beyond)", 61st IEEE Annual Symposium on Foundations of Computer Science, pp. 577–588, arXiv: 2003.04280 , doi:10.1007/978-3-540-75520-3_52 .
18. Rivest, Ronald L.; Vuillemin, Jean (1975), "A generalization and proof of the Aanderaa-Rosenberg conjecture", Proc. 7th ACM Symposium on Theory of Computing , Albuquerque, New Mexico, United States, pp. 6–11, doi:10.1145/800116.803747, S2CID   16220596 .
19. Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), "A topological approach to evasiveness", Symposium on Foundations of Computer Science , Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, doi:10.1109/SFCS.1983.4 .
20. Bender, Michael A.; Ron, Dana (2000), "Testing acyclicity of directed graphs in sublinear time", Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., vol. 1853, Berlin: Springer, pp. 809–820, doi:10.1007/3-540-45022-X_68, MR   1795937 .