Implicit graph
Encyclopedia
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 algorithm
ically from some more concise input.
s 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. 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.
In computational complexity theory
, several complexity class
es 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 -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 graph
s that has attracted attention in algorithmic game theory
because it contains the problem of computing a Nash equilibrium
. 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 -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. PLS
, another complexity class, captures the complexity of finding local optima in an implicit graph.
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.
: it is straightforward to check whether two vertices are adjacent but finding the neighbors of any vertex requires a search through all possible vertices.
Graph families with adjacency labeling schemes include:
Not all graph families have local structures. For some families, a simple counting argument proves that adjacency labeling schemes do not exist: only bits may be used to represent an entire graph, so a representation of this type can only exist when the number of -vertex graphs in the given family is at most . Graph families that have larger numbers of graphs than this, such as the bipartite graph
s or the triangle-free graph
s, do not have adjacency labeling schemes. 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 -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. Kannan et al. asked whether having a forbidden subgraph characterization and having at most -vertex graphs are together enough to guarantee the existence of an adjacency labeling scheme; this question, which Spinrad restated as a conjecture, remains open.
If a graph family has an adjacency labeling scheme, then the -vertex graphs in may be represented as induced subgraphs of a common universal graph
of polynomial size, the graph consisting of all possible vertex identifiers. Conversely, if a universal graph of this type can be constructed, then the identities of its vertices may be used as labels in an adjacency labeling scheme. 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 universal graph. Alstrup and Rauhe showed that any tree has an adjacency labeling scheme with bits per label, from which it follows that any graph with arboricity
k has a scheme with bits per label and a universal graph with vertices. In particular, planar graphs have arboricity at most three, so they have universal graphs with a nearly-cubic number of vertices.
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; 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—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 graph
s from graphs that are very far from being acyclic. In contrast, such a fast time is not possible in neighborhood-based implicit graph models,
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
ically from some more concise input.
Neighborhood representations
The notion of an implicit graph is common in various search algorithmSearch algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
s 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. This type of implicit graph representation is analogous to an adjacency list
Adjacency list
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node...
, 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
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
, 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.
In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, several complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es 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
PPA (complexity)
PPA is a complexity class, standing for "Polynomial Parity Argument" . Introduced by Christos Papadimitriou in 1994 , PPA is a subclass of TFNP...
is the class of problems in which one is given as input an undirected implicit graph (in which vertices are -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
Handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...
, such a vertex exists; finding one is a problem in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, but the problems that can be defined in this way may not necessarily be NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, as it is unknown whether PPA = NP. PPAD
PPAD (complexity)
PPAD is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument...
is an analogous class defined on implicit directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s that has attracted attention in algorithmic game theory
Algorithmic game theory
Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal...
because it contains the problem of computing a Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
. The problem of testing reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
of one vertex to another in an implicit graph may also be used to characterize space-bounded nondeterministic complexity classes including NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
(the class of problems that may be characterized by reachability in implicit directed graphs whose vertices are -bit bitstrings), SL
SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...
(the analogous class for undirected graphs), and PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
(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. PLS
PLS (complexity)
In computational complexity theory, PLS, which stands for Polynomial Local Search, is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem....
, another complexity class, captures the complexity of finding local optima in an implicit graph.
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
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
but that requires exponential time to solve on any classical computer.
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 in a given family of graphs to be an assignment of an -bit identifier to each vertex of , together with an algorithm (that may depend on but is independent of the individual graph ) that takes as input two vertex identifiers and determines whether or not they are the endpoints of an edge in . That is, this type of implicit representation is analogous to an adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
: it is straightforward to check whether two vertices are adjacent but finding the neighbors of any vertex requires a search through all possible vertices.
Graph families with adjacency labeling schemes include:
- Sparse graphs. If every vertex in has at most neighbors, one may number the vertices of from 1 to and let the identifier for a vertex be the -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 arboricityArboricityThe arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
or bounded degeneracyDegeneracy (graph theory)In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate...
, including the planar graphPlanar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s and the graphs in any minor-closed graph familyRobertson–Seymour theoremIn graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
. - Intersection graphs. An interval graphInterval graphIn graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
is the intersection graphIntersection graphIn the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of a set of line segmentLine segmentIn geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s in the real lineReal lineIn mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
. 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 boxicityBoxicityIn graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes...
and the circle graphCircle graphIn graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.-Algorithmic...
s, and subfamilies of these families such as the distance-hereditary graphDistance-hereditary graphIn graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...
s and cographCographIn graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s. 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 graphUnit disk graphIn geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other....
may require exponentially many bits for the coordinates of the disk centers. - Low-dimensional comparability graphs. The comparability graphComparability graphIn graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
for a partially ordered setPartially ordered setIn mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
has a vertex for each set element and an edge between two set elements that are related by the partial order. The order dimensionOrder dimensionIn mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
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 chordalChordal graphIn the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
comparability graphComparability graphIn graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
s, which come from partial orders of dimension at most four.
Not all graph families have local structures. For some families, a simple counting argument proves that adjacency labeling schemes do not exist: only bits may be used to represent an entire graph, so a representation of this type can only exist when the number of -vertex graphs in the given family is at most . Graph families that have larger numbers of graphs than this, such as the bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
s or the triangle-free graph
Triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
s, do not have adjacency labeling schemes. 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 -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. Kannan et al. asked whether having a forbidden subgraph characterization and having at most -vertex graphs are together enough to guarantee the existence of an adjacency labeling scheme; this question, which Spinrad restated as a conjecture, remains open.
If a graph family has an adjacency labeling scheme, then the -vertex graphs in may be represented as induced subgraphs of a common universal graph
Universal graph
In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado and is now called the Rado graph or random graph...
of polynomial size, the graph consisting of all possible vertex identifiers. Conversely, if a universal graph of this type can be constructed, then the identities of its vertices may be used as labels in an adjacency labeling scheme. 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 universal graph. Alstrup and Rauhe showed that any tree has an adjacency labeling scheme with bits per label, from which it follows that any graph with arboricity
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
k has a scheme with bits per label and a universal graph with vertices. In particular, planar graphs have arboricity at most three, so they have universal graphs with a nearly-cubic number of vertices.
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 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. This difference allows every graph to have 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 the implementation of that test.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; 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—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 graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
s from graphs that are very far from being acyclic. In contrast, such a fast time is not possible in neighborhood-based implicit graph models,