PQ Trees, PC Trees, and Planar Graphs:Introduction and The Consecutive-Ones Problem
Introduction
A graph is planar if it is possible to draw it on a plane so that no edges intersect, except at endpoints. Such a drawing is called a planar embedding.
Not all graphs are planar: Figure 32.1 gives examples of two graphs that are not planar. They are known as K5 , the complete graph on five vertices, and K3,3, the complete bipartite graph on two sets of size 3. No matter what kind of convoluted curves are chosen to represent the edges, the attempt to embed them always fails when the last of the edges cannot be inserted without crossing over some other edge, as illustrated in the figure.
There is considerable practical interest in algorithms for finding planar embeddings of planar graphs. An example of an application of this problem is where an engineer wishes to embed a network of components on a chip. The components are represented by wires, and no two wires may cross without creating a short circuit. This problem can be solved by treating the network as a graph and finding a planar embedding of it. Planar graphs play a central role in geographic information systems, and in many problems in computational geometry.
The study of planar graphs dates to Euler. The faces of an embedding are connected regions of the plane that are separated from each other by cycles of G. Euler showed that for any planar embedding, if V is the set of vertices, E the set of edges, F the set of faces (regions of the plane that are connected in the embedding), and C the set of connected
components of the graph, then |V | + |F | = |E| + |C| + 1. Many other results about planar
FIGURE 32.1: Two non-planar graphs. The first is the K5, the complete graph on five vertices, and the second is the K3,3, the complete bipartite class on two sets of three vertices each. Any attempt to embed them in the plane fails when a final edge cannot be inserted without crossing the boundary between two faces.
graphs can be proven using this formula. For instance, using the formula, it is easily proven with counting arguments that K5 and K3,3 are non-planar [12].
The famous 4-color theorem states that the vertices of a planar graph can always be partitioned into four independent sets; an equivalent statement is that a mapmaker never needs to use more than four colors to color countries on a map so that adjacent countries are of different colors. It remained open in the literature for almost 100 years and was finally proven with the aid of a computer program in 1976 [1, 2].
A subdivision of an edge xy of a graph is obtained by creating a new node z, and replacing xy with new edges xz and zy. The inverse of this operation is the contraction of z, and only operates on vertices of degree 2. A subdivision of a graph is any graph that can be obtained from it by a sequence of subdivision operations. Since K5 and K3,3 are non-planar, it is obvious that subdivisions of these graphs are also non-planar. Therefore, a graph that has a subgraph that is a subdivision of K5 or K3,3 as a subgraph must be non-planar. Such a subgraph is said to be homeomorphic to a K3,3 or a K5.
A famous results in graph theory is the theorem of Kuratowski [21], which states that the absence of a subdivision of a K5 or a K3,3 is also sufficient for a graph to be planar. That is, a graph is planar if and only if it has no subgraph that is a subdivision of K3,3 or K5. Such a subdivision is known as a Kuratowski subgraph.
A certifying algorithm for a decision problem is one that produces an accompanying piece of evidence, or certificate that proves that its answer is correct. The certificate should be simple to check, or authenticate. Certifying algorithms are highly desirable in practice, where the possibility must be considered that an implementation has a bug and a simple yes or no answer cannot be entirely trusted unless it is accompanied by a certificate. The issue is discussed at length in [20]. Below, we describe a certifying algorithm for recognizing planar graphs. The algorithm produces either a planar embedding of the graph, proving that the graph is planar, or points out a Kuratowski subgraph, proving that it is not.
Next, let us consider a problem that is seemingly unrelated to that of finding a planar embedding of a graph, but which can be solved with similar data structures. Given a set S of intervals of a line, let their interval graph be the graph that has one vertex for each of the intervals in S, and an edge between two vertices if their intervals intersect. That
FIGURE 32.2: An interval graph is the intersection graph of a set of intervals on a line. There is one vertex for each of the intervals, and two vertices are adjacent if and only if the corresponding intervals intersect.
is, a graph is an interval graph if it is the intersection graph of a set of intervals on a line. Figure 32.2 gives an illustration.
Interval graphs also come up in a variety of other applications, such as scheduling jobs that conflict if they must be carried out during overlapping time intervals. If an interval representation is given, otherwise NP-complete problems, such as finding a maximum independent set, can be solved in linear time [9].
Given the intervals, it is trivial to construct their interval graph. However, we are interested in the inverse problem, where, given a graph G, one must find a set of intervals that have G as their interval graph or else determine that G is not an interval graph.
Interest in this problem began in the late 1950’s when the noted biologist Seymour Benzer used them to establish that genetic information is stored inside a biological structure that has a linear topology [3]; this topology arises from the now-familiar structure of DNA. To do this, he developed methods of inducing mutations using X-ray photons, which could be assumed to reflect damage to a contiguous region, and for testing whether two of these mutations had common effects that indicated that the the damaged regions intersect. This gave rise naturally to a graph where each mutation is a vertex and where two vertices have an edge between them if they intersect. He got the result by showing that this graph is an interval graph.
Let us say that such a set S is a realizer of the interval graph G if G is S’s interval graph. Benzer’s result initiated considerable interest in efficient algorithms to finding realizers of interval graphs, since they give possible linear orderings of DNA fragments, or clones, given data about which fragments intersect [5, 10, 11, 16, 17, 19, 26–28]. A linear-time bound for the problem was first given by Booth and Lueker in [5]. Though the existence of forbidden subgraphs of interval graphs has long been well-known [22], the first linear-time certifying algorithm for recognizing interval graphs has only been given recently [20]; the certificate of acceptance is an interval realizer and the certificate of rejection is a forbidden subgraph. When the ordering of intervals is unique except for trivial details, such as the lengths of the intervals and the relative placement of endpoints that intersect, this solves the physical mapping problem on DNA clones: it tells how the clones are arranged on the genome. Effi- cient algorithms for solving certain variations of this problem played a role in the assembling the genomes of organisms, and continue to play a significant role in genetic research [39].
For input data containing errors, Lu and Hsu [23] give an error-tolerant algorithm for the clone assembly problem.
A graph is a circular-arc graph if it is the intersection graph of a set of arcs on a circle. Booth conjectured that recognizing whether a graph is a circular-arc graph would turn out to be NP complete [4], but Tucker later found a polynomial-time algorithm [38]. McConnell has recently found a linear-time algorithm [29]. The problem of finding a certifying algorithm
FIGURE 32.3: The clique matrix of a graph has one row for each vertex, one column for each maximal clique, and a 1 in row i column j iff vertex i is contained in clique j. The maximal cliques of an interval graph correspond to points of maximal overlap in an interval representation. Ordering the columns of a clique matrix in the order in which they appear in an interval representation gives a consecutive-ones ordering of the clique matrix.
for the problem remains open.
Finding the maximal cliques of an arbitrary graph is hard: in fact it is NP complete to find whether a graph has a clique of a given size k. However, if a graph is chordal it is possible to list out its maximal cliques in linear time [32], and interval graphs are chordal. (A chordal graph is one that has no simple cycle on four or more vertices as an induced subgraph.) We may therefore create a clique matrix, which has one row for each vertex of the graph, one column for each maximal clique, and a 1 in row i, column j iff clique j contains vertex i.
THEOREM 32.1 A chordal graph is an interval graph iff there is a way to order the columns of its clique matrix so that, in every row, the 1’s are consecutive.
To see this, suppose G is an interval graph and S is a realizer. Then, for each maximal clique C, a clique point on the line can be selected that intersects the intervals that correspond to elements of C and no others. (See Figure 32.3.) Ordering the columns of the clique matrix according to the left-to-right order of the corresponding clique points ensures that the 1’s in each row will be consecutive. Conversely, given a consecutive-ones ordering, the 1’s in each row occupy an interval on the sequence of columns. It is easy to see that these intervals constitute a realizer of G, since two vertices are adjacent iff they are members of a common maximal clique.
Such an ordering of the columns of a 0-1 matrix is known as a consecutive-ones ordering, and a 0-1 matrix has the consecutive-ones property if there exists a consecutive-ones ordering of it. The main thrust of Booth and Lueker’s algorithm consists of an algorithm for determining whether there exists a a consecutive-ones ordering of the columns of a 0-1 matrix. Their algorithm operates on a sparse representation of the matrix, and solves this in time linear in the number of 1’s in the matrix. To test for the consecutive-ones property, they developed a representation, called a PQ tree, of all the consecutive-ones orderings of the columns. The tree consists of P nodes and Q nodes. The leaves of the tree are columns of the matrix, and the left-to-right leaf order of the tree gives a consecutive-ones ordering, just as it does when the order of children of a node are reversed, or when the order of chil- dren of a P node are permuted arbitrarily (see Figure 32.4). All consecutive-ones orderings of the columns can be obtained by a sequence of such rearrangements.
The PQ tree helps with keeping track of possible consecutive-ones orientations as they work by induction on the number of rows of the matrix. Each interval realizer of G is given
FIGURE 32.4: The leaves of a PQ tree are the columns of a consecutive-ones matrix. The left-to-right order of the leaves gives a consecutive-ones arrangement of the columns. So does the result of reversing the leaf descendants of a node. The order of leaves of a consecutive set of children of a P node can also be reversed to obtain a new consecutive-ones ordering. All consecutive-ones orderings can be obtained by a sequence of these reversals.
by a consecutive-ones ordering, except for minor details that do not affect the order of clique points.
The literature on problems related to PQ trees is quite extensive. Korte and Mo¨hring [19] considered a modified PQ tree and a simpler incremental update of the tree. Klein and Reif [18] constructed efficient parallel algorithms for manipulating PQ trees. Hsu gave a simple test that is not based on PQ trees [15].
McConnell gives a generalization of the PQ tree to arbitrary 0-1 matrices, gives a linear- time algorithm for producing it, and a linear-time certifying algorithm for recognizing the consecutive-ones property [25].
The PQ tree play an important role in the linear-time algorithm of Lempel, Even, and Cederbaum for finding a planar embedding of planar graphs [24]. The algorithm takes advantage of the PQ tree’s rich ability to represent families of linear orderings in order to keep track of possible arrangements of edges in an embedding of G.
Booth and Lueker’s algorithm for constructing the PQ tree has a reputation for being difficult to understand and to program, and the many algorithms that have appeared since reflect an effort to address this concern. Their algorithm builds the tree by induction on the number of rows of the matrix. For each row, it must perform a second induction from the leaves toward the root. At each node encountered during this second induction, it uses one of nine templates for determining how the tree must change in the vicinity of the node. Recognizing which template must be used is quite challenging. Each template is actually a representative of a larger set of cases that must be dealt with explicitly by a program.
These templates carry over into the use of the PQ tree in planar graph embedding.
The PC tree is an alternative introduced by Shih and Hsu [34] to address these difficulties. It is essentially the result of “unrooting” the PQ tree to obtain a free tree that awards no special status to any root node, and where notions of “up” and “down” in the tree have no meaning. This introduces a symmetry to the problem that is otherwise broken by the choice of the root, and once it is introduced, the various templates collapse down to a single case.
This suggests that the cases that must be considered in the templates are an artifact of an arbitrary choice of a root in the tree. The reason that this was not recognized earlier may have more to do with the fact that rooted trees are ubiquitous as data structures, whereas free trees are not commonly used as data structures. The need to root such a data may simply have been an assumption that people failed to scrutinize.
A matrix has the circular-ones property if the columns can be ordered so that, in every row, either the zeros are consecutive or the ones are consecutive. That is, it has the circular-ones property if the ones are consecutive when the matrix is wrapped around a vertical cylinder, which has the effect of eliminating any special status to any column, such as being the leftmost column.
Hsu [14] gives an algorithm using PC trees for solving the consecutive-ones problem. Hsu and McConnell [17] have shown that that both the PQ tree and the PC tree have remarkably simple definitions as mathematical objects. They are each precisely given by previously-known theorems on set families that had not previously been applied in this domain. Moreover, we show that the PC tree gives a representation of all circular-ones orderings of a matrix just as the PQ tree gives a representation of all consecutive-ones orderings.
Figure 32.5 illustrates how the PC tree represents the circular-ones orderings. The leaves are the columns of the matrix, and are arrayed around the large circle, which represents the circular ordering. The C nodes (double circles) have a cyclic order on their edges that can be reversed. We could think of them as coins with edges attached at discrete points around the sides, and that can be turned heads-up or tails-up, an operation that we will call a flip. The P nodes (black internal nodes) have no cyclic ordering. The circular-ones orderings of the columns of the matrix are just those that result from planar embeddings of this gadget that put the leaves on the outer circle. This description makes it obvious what family of circular orderings is represented: you can select an edge and reverse the order of all leaves that lie on one side of the edge, or you can reverse the order of a consecutive set of leaves if they are the leaves of a subset of the trees in the forest that would result from the removal of a P node.
Booth and Lueker showed that testing for the circular-ones property reduces in linear time to testing for the consecutive-ones property. It appears to be more natural to perform the reduction in the opposite direction. That is, to solve the consecutive-ones problem reduce it to the circular-ones problem, which can be solved with the PC tree instead of with the PQ tree. To do this, just add the zero vector as a new column of the matrix, compute the PC tree for the new matrix, and then pick it up by the leaf corresponding to the new column to root it. (See Figure 32.6.) In [17], it is shown that the subtree rooted at its child is the PQ tree for the original matrix.
The Consecutive-Ones Problem
In this section, we give an algorithm that is related to Booth and Lueker’s algorithm, except that it uses the PC tree in place of the PQ tree.
FIGURE 32.5: The PC tree can be viewed as a gadget for generating the circular-ones orderings of the columns. The C nodes are represented by double circles and the P nodes are represented by black dots. The subtree lying at one side of an edge can be flipped over to reverse the order of its leaves. The order of leaves of a consecutive set of subtrees that would result from the removal of a P node can also be reversed. All circular-ones orderings can be obtained by a sequence of such reversals.
Let us say that two subsets X and Y of a domain V strongly overlap if X∩Y , X−Y ∪Y −X, and V − X − Y are all nonempty. We view the columns of a 0-1 matrix as a set V , and each row of the matrix as a subset of V consisting of those columns where there is a 1 in the row.
A set X is an edge module if it is the union of leaves in one of the two subtrees that results when an edge is removed. It is a P module if it is not an edge module but the union of leaves in a subset of the trees formed when a P node is removed. An edge or P module is an unrooted module. The key to understanding the construction of the PC tree is the fact that the unrooted modules are precisely those nonempty proper subsets of V that do not strongly overlap any row of the matrix.
We construct the PC tree by induction on the number of rows of a matrix. The ith step of the algorithm modifies the PC tree so that it is correct for the submatrix consisting of the first i rows of the matrix. As a base case, after the first step, the PC tree consists of two adjacent P nodes, with one of them adjacent to the leaves that correspond to ones in the first row and the other adjacent to the leaves that correspond to the zeros.
During the ith step, no new unrooted modules are created by adding a row, but some unrooted modules in the first i − 1 rows may become defunct as unrooted modules once the ith row is considered. It is necessary to modify the tree so that it no longer represents these sets as unrooted modules.
Let the full leaves denote the leaves that correspond to ones in row i, and let the empty leaves denote those that correspond to zeros in row i. If an edge module X becomes defunct in the ith step, then X and X each contain both empty leaves and full leaves. Then X corresponds to an edge whose removal separates the PC tree into two trees, each of which has both full and empty leaves. Let us call such an edge a terminal edge. Terminal edges must be removed from the tree, since they correspond to defunct edge modules. If M has the circular ones property, these terminal edges form a path (See Figure 32.7). Let us call this path the terminal path. The terminal nodes are the nodes that lie at the ends of the terminal path. All nodes and edges that must be altered in Step i lie on the terminal path. When there is a unique node of the PC tree that has both full and empty neighbors, we consider it to be a terminal path of length 0; this node assumes the role of both terminal nodes.
Algorithm 32.2 Constructing the PC Tree
The initial PC tree is a P node that is adjacent to all leaves, which allows all (n − 1)! circular orderings.
At each row:
• Find the terminal path, and then perform flips of C nodes and modify the cyclic order of edges incident to P nodes so that all ones lie on one side of the path (see Figure 32.8.)
• Split each node on the path into two nodes, one adjacent to the edges to full leaves and one adjacent to the edges to empty leaves.
• Delete the edges of the path and replace them with a new C node x whose cyclic order preserves the order of the nodes on this path.
• Contract all edges from x to C-node neighbors, and any node that has only two neighbors.
FIGURE 32.7: The edges that must be modified when a new row is added are those that represent two sets that have a mixture of zeros and ones, as these sets fail the criterion for being unrooted modules in the new row. If the matrix has the circular-ones property, these edges lie on a path, called the terminal path. The terminal nodes are the nodes t1 and t2 that lie at the ends of the terminal path.
FIGURE 32.8: To update the PC tree when a new row is added to the matrix, flip the C nodes and order the P nodes on the terminal path so that the edges that go to trees whose leaves are zeros in the row lie on one side (white) and those that go to trees whose leaves are ones in the row lie on the other side (black). This is always possible if the new matrix has the circular-ones property (Figure A). Then divide each node on the terminal path into two parts, one that is adjacent to the black trees and one that is adjacent to the white trees (Figure B). Replace the edges of these two paths with a new C node, x, whose cyclic order reflects the order of nodes these two paths. Finally, contract each edge from x to a C-node neighbor, and contract each internal node of degree two (Figure C).
FIGURE 32.9: An order-preserving contraction of an edge xy. The neighbors of x and y are cyclically ordered. The edge is removed and x and y are identified, so that the cyclic order of neighbors of x and y about the edge is preserved.
A Data Structure for Representing the PC Tree
For the implementation, we pair up the n−1 edges with n−1 of the nodes of the tree, so that each edge is paired with one of the nodes that it is incident to. This can be accomplished by rooting the tree at an arbitrary node in order to define a parent function, and then pairing each non-root node with its parent edge. It is worth noting that in contrast to the rooting of the PC tree, which serves to give a distinguished role to the root, the sole purpose of this is to make low-level operations more efficient. An example of such an operation is the problem of finding out whether two nodes of an unrooted tree are adjacent, which can be determined in O(1) time if it is rooted, by examining the parent pointers of the two nodes. An undirected graph is a special case of a directed graph where every arc (u, v) has a twin arc (v, u). Thus, we may speak of the directed arcs of the PC tree, not just its edges.
DEFINITION 32.1 The data structure for the PC tree is the following. Each P node carries a pointer to the parent edge. Each edge uv is implemented with two oppositely directed twin arcs (u, v) and (v, u). Each arc (x, y) has a pointer to its two neighbors in the cyclic order about y, a pointer to its twin, and a parent bit label that indicates whether y is the parent of x. In addition, if y is a P node, then (x, y) has a pointer to y. There is no explicit representation of a C node; its existence is implicit in the doubly-linked circular list of its incident edges that gives their cyclic order. No two C nodes are adjacent, so each of these edges has one end that identifies a neighbor of the C node, and another end that indicates that the end is incident to a C node, without identifying the C node.
If (x, y) is an arc directed into y and y is a C node, then y is not represented by an explicit record. We can find y’s parent edge by cycling through the the records for arcs that are directed into y in either cyclic direction about y, until we reach an arc with the required parent bit. Thus, finding a C node’s parent edge is not an O(1) operation.
The data structure makes no distinction between the two directions in which a list can be traversed; this distinction is made only at the time when a traversal is begun. One must keep track of both the current and previous element. To move to the next element, one must retrieve both neighbors of the current element, and select the one that is different from the previous element.
Since we will deal with unrooted trees whose internal nodes can be cyclically ordered, it will be useful to define the cyclic order of edges incident to z after the contraction. An order-preserving contraction is the one depicted in Figure 32.9, where the neighbors x and y are each consecutive and preserve their original adjacencies in the circular order of z’s neighbors.
Using this data structure, it takes O(1) time to remove or insert a section of a list, given pointers to the endpoints. Since the list draws no distinction between forward and backward, a section of a list can be inserted in either order in O(1) time. It therefore supports an order-preserving contraction of an edge between two adjacent C nodes x and y in O(1) time, given a pointer to (x, y), in addition to allowing insertion or removal of an edge from a node’s circular adjacency list or reversal of a section of a circular list in O(1) time
Finding the Terminal Path Efficiently
Finding the terminal path is the only step where pointers to parent edges are required in the ith iteration.
Recall that we have defined full and empty leaves of the PC tree. For the internal nodes, let us say that a node is full if it is possible to root the tree so that all leaves in the subtree rooted at the node are full, and empty if it is possible to root the tree so that all leaves in its subtree are empty. Since each node has degree at least three, at most one of these designations applies at a node.
We use the following full-partial labeling algorithm to mark the full nodes. The efficiency of the algorithm is due to the fact that it avoids touching some of the empty nodes; it leaves them unmarked. We label a leaf as full if it corresponds to a column with a one in the ith row. We label an internal node as full if all of its neighbors except one have been labeled full. We label an internal node as partial if at least one of its neighbors has been labeled full. Whenever we label a node as full, we increment a counter in its non-full neighbor x that records how many full neighbors x has, labeling x as full if this counter rises to one less than the degree of x. However, if x is a C node, then since it is given implicitly by a circular list of neighbors, we do not keep an explicit counter at x. Nevertheless, it is easy to detect when all of its neighbors except one is full. Recall that no two C nodes are adjacent. To perform the labeling in the presence of C nodes, we use an unrooted variant of the pointer borrowing strategy of [5]. We maintain block-spanning pointers from the first to last vertex and from the last to the first vertex in each consecutive block of full neighbors around the cycle that makes up x. Each time a new y neighbor of x becomes full, either y becomes a one-element block, a block is extended by appending or prepending y, or two blocks and y merged, by appending y to one of the blocks and prepending it to the other. Each of these operations gives access in O(1) time to the first or last vertex in each affected block, so it is trivial to update the block-spanning pointers in O(1) time. A test of whether the first and last vertices in the resulting block share a non-full neighbor z on the cycle takes O(1) time. If x passes this test, it is full, and the full-neighbor counter of z is incremented. Since every node of the PC tree has degree at least three, the number of full leaves is at least as great as the number of full internal nodes, and there are at most k full leaves. Assigning full labels takes O(k) time. The number of partial nodes is at most as great as the number of full nodes, since each full node has at most one partial neighbor. Assigning partial labels takes O(k) time also.
Henceforth, let us call a node full or partial according to the final label assigned to it by the full-partial labeling algorithm.
The key insight for finding the terminal edges is the observation that an edge is terminal if and only if it lies on a path in the tree between two partial nodes.
In the special case where there are no terminal edges and the terminal path has length 0, it is the unique node that has both full and unmarked neighbors. It is easy to see that since there are no other such nodes, its unmarked neighbors are empty. This node is easy to find, given the marking of the nodes.
Otherwise, let the apex be the least common ancestor of the partial nodes. We find the terminal edges by starting at each partial node and extending a path up through its ancestors, marking edges on the path. We do this in parallel at all partial nodes, extending the paths at the same rate. When a path runs into another partial node, we stop extending that path. If a path extends above the apex, we may or may not detect this right away. Eventually, we will be extending only one path, at which point, the marked edges form a connected subtree. The apex is the first point below the highest point of this subtree that is either partial or has two paths entering it. Unmarking the edges from the marked edge down to the apex leaves edges marked iff they are terminal edges.
If x is a node on the terminal path other than the apex, then the parent of x is also on the terminal path. If x is a P node, this takes O(1) time, since it has a pointer to its parent. If x is a partial C node that has a full neighbor, we may assume that we have a pointer to the edge to this neighbor, since this is provided by the full-partial labeling algorithm. This is always the case at a terminal node, which has a full neighbor and an empty neighbor. As we climb the terminal path toward the apex, when reaching a C node y from its child x on the terminal path, we obtain a pointer to the edge (x, y), since x is a P node and (x, y) is its parent edge. We obtain pointer even if y has no full neighbor.
The key to bounding the cost of finding x’s parent when x is a C node on the terminal path is the observation that if it has any full neighbors, the full neighbors are consecutive, and the edges to its neighbors on the terminal path are adjacent to the full neighbors in the cyclic order. Thus, if it has no full neighbor, we can look at the two neighbors of the child edge in the cyclic order, and one of them must be the parent edge. This takes O(1) time. If x has a full neighbor, then we can cycle clockwise and counterclockwise through the edges to full neighbors. Of the first edges clockwise and counter-clockwise that are not to full neighbors, one of these is the parent. In this case, the cost of finding the parent is proportional to the number of full neighbors x.
If x does not lie on the terminal path, then this procedure may fail, in which case we detect that it is not on the terminal path, or it may succeed, in which case we can bound the cost of finding the parent in the same way.
If the union of all paths traversed has pi nodes and there are k ones in row i, then the total cost is O(pi + k). However, the number of nodes in these paths that are not on the terminal path is at most the number of nodes that are on the terminal path, because of the way the paths are extended in parallel. The following summarizes these observations.
LEMMA 32.1 If the terminal edges form a path and the full and empty neighbors can be flipped to opposite sides of it, then finding the terminal path in the ith step takes O(p + k) time, where p is the length of the terminal path and k is the number of full nodes.
If the conditions of the lemma are not satisfied, the matrix does not have the circular-ones property, and is rejected.
Performing the Update Step on the Terminal Path Efficiently
The number of full neighbors of nodes on the terminal path is bounded by the number k of ones in the ith row. Before splitting a node, we record its neighbors on the terminal path, and then delete the edges to these neighbors, in O(1) time. We then split the node by splicing out the full neighbors, and forming a new node with them. The remainder of the old node serves as the other half of the split. This takes time proportional to the number of full neighbors. Since the number of full neighbors of nodes on the terminal path is bounded by the number of ones in the ith row, the total time for this is O(p + k). Creating the new C node x and installing edges to the split nodes in the required cyclic order then takes O(p) time.
Since our data structure includes a parent function, we must assign the parent bits to the new edges. Let y be the copy of the apex that retains its parent edge after the split of the apex. Except in the case of the apex, the parent edge of every vertex on the terminal path is an edge of the terminal path, and these edges have been deleted. Thus, none of these nodes have a parent edge. We make x the new parent of these nodes, and we let y be the parent of x. This takes O(p) time by setting the appropriate bits in the O(p) edges incident to x.
The operation of deleting a C node z from x’s neighborhood and replacing it with the neighbors of z is just a contraction of the edge xz, depicted in Figure 32.9, which takes O(1) time. These observations can be summarized as follows:
LEMMA 32.2 Updating the tree during the ith step takes O(p + k) time, where p is the length of the terminal path and k is the number of full nodes.
Assume that the matrix is given in sparse form, where, for each row, the set of columns where the row has a one is listed. Let us assume that every row and every column has at least one nonzero entry, since it can otherwise be eliminated in a preprocessing step. A linear time bound is one that is proportional to the number of nonzero entries in the matrix. The algorithm processes one row at a time of the matrix M . Let T denote the current state of the PC tree after the first i rows have been processed. That is, T is the PC tree for the submatrix induced by the first i rows. Let Ci be the set of C nodes and let Pi be the set of Pi nodes in T , and let ui be the number of ones in the rows of the matrix that have not yet been processed. If x is a node of T , let deg(x) denote the degree, or number of neighbors of x in T .
If, when processing a row, we could update the PC tree in time proportional to the number of ones in the row, the linear time bound would be immediate. Unfortunately, the update step does not conform to this bound. Therefore, we use a technique called amortized analysis [9], which uses an accounting scheme whereby updates that exceed this bound borrow credits from updates that were completed with time to spare. The analysis shows that, even though there is variability in the time required by the updates, the aggregate cost of all updates is linear.
We adopt a budget where we keep an account that must have a number of credits φ(M, i)
in reserve, where φ(N, i) is given by the following:
Such a function is often called a potential function. Each credit can pay an O(1) operation. Any operation that reduces φ allows us to withdraw credits from the account to pay for some of the operations. Since φ(M, 0) is Θ(m), we must pre-pay the cost of later operations by making a deposit of Θ(m) credits to the account. If we can maintain this reserve as we progress and still pay for all operations with withdrawals, then, since φ never runs the account to zero, the running time of the algorithm is O(m).
To cover the costs in row i, we must be able to withdraw k + p credits, by Lemmas 32.1 and 32.2, where k is the number of full nodes. Since every full node has at least two full neighbors, the number of marked nodes is at most two times the number of 1’s in row i, so k credits are freed up by the decrease from 2ui to 2ui+1.
Each C node on the terminal path is first split, but then both of these copies are contracted. This decreases the number of C nodes by one without changing the degrees of any P nodes, so spending a credit for each C node on the path is within the budget. Suppose a P node does not lie at the end of the terminal path. If it is split, the sum of degrees of the two parts is the same as the degree of the original, after the terminal-path edges are deleted and replaced with an edge to the new C node. However, in calculating φ, subtracting one from the degrees of two P nodes instead of one frees a credit. If the P node has only empty neighbors or only full neighbors, it is not split. In this case its degree decreases by one when its two incident terminal-path edges are deleted and replaced by a single edge to the new C node. A P node at the end of the terminal path fails to free up a credit, but there are only O(1) of these. Contractions of nodes of degree two free up a credit, whether they are C nodes or P nodes. Θ(k + p) credits for row i can be paid out while adhering to the budget.
Comments
Post a Comment