15896133
Worst-Case Analysis of Read's Chromatic Polynomial Algorithm
The worst-case time-complexity of Read's edge-addition/contraction algorithm for computing the chromatic polynomial of an n-vertex graph is shown to be O(n2B(n)), where B(n) is the nth Bell number, which grows faster than cn for any c but slower than n!. The factor n2 can be reduced to n, and the space-complexity from O(n3) to O(n2), by storing in arrays the information needed to reverse each transformation made on the graph. A graph G is assumed to be finite (with n vertices), unoriented and without loops or parallel edges. A t-colouring of G is a mapping from the vertex-set of G into the set {1,...,t} of colours so that no two adjacent vertices have the same colour. The chromatic polynomial P(G,t) of G is a function of t whose value for a given t is the number of t-colourings of G. Once the polynomial P(G,t) has been calculated, one can decide in polynomial time if G has a t-colouring for a given t by substituting t into the polynomial: G has a t-colouring if and only if P(G,t)>0. Since the problem of deciding whether G has a t-colouring is NP-hard [1, p. 392], it is unlikely that a polynomial-time algorithm will be found for computing the chromatic polynomial of a graph. The most commonly-used algorithm is the one proposed by Read [3]. It has been referenced and improved upon in several places in the literature (see, for example [5]) but its worst-case timeand spacecomplexity have never been published. We show here that the spacecomplexity is O(n3) and the time-complexity is O(n2B(n)), where B(n), the nth Bell number, grows faster than cn for any c but slower than n!, and we modify the algorithm so that it runs in O(nB(n)) time and uses O(n2) space. The following facts are shown in [3] and in other places: 1. P(G,t) is a polynomial of degree n in t. 2. If G is a tree then P(G,t)=t(t-1)n-1. 3. If G is not connected then the chromatic polynomial of G is the product of the chromatic polynomials of its connected components. 4. If G is a complete graph then P(G,t) = t(t-1)(t-2)...(t-n+1). (1) 5. If G is not a complete graph, let x and y be any two non-adjacent vertices. Let G+{x,y} be the graph obtained from G by adding the edge {x,y} to G. Let G(x=y) be the graph obtained from G by identifying the vertices x and y, where a vertex v is adjacent to the common vertex xy in G(x=y) if and only if v is adjacent to at least one of x and y in G. Then P(G,t) = P(G+{x,y},t) + P(G(x=y),t). (2) The algorithm in [3] for calculating P(G,t) is a recursive one based on (1) and (2). We give a non-recursive version (see Figure 1) for the purpose of analysing its spaceand time-complexity. Procedure PolyChrome(G: n-vertex graph; C: ARRAY[1..n] OF INTEGER); FOR i:=1 TO n DO C[i]:=0 END FOR; m:=n; H:=G; (* H is the current graph, which has m vertices *) Stack:=EMPTY; LOOP IF H has two non-adjacent vertices x and y THEN PUSH H+{x,y} onto Stack; H:=H(x=y); m:=m-1; ELSE C[m]:=C[m]+1; IF m<n THEN POP from Stack into H; m:=m+1; ELSE EXIT END IF END IF END LOOP END PolyChrome. Figure 1 A non-recursive version of Read's chromatic polynomial algorithm. We find P(G,t) from formula (3) below: P(G,t) = C[1]t + C[2]t(t-1) + ... + C[n]t(t-1)...(t-n+1). (3) We analyse the spaceand time-complexity of this algorithm under the assumption that the graph is represented by an adjacency matrix. The space-complexity is easy to analyse: at any time the stack will contain one graph with i vertices for each i from n down to m for a maximum of n graphs, each occupying O(n2) space, for a total of O(n3). To analyse the time-complexity we note that everything done to a graph H creating it, searching it for non-adjacent vertices, pushing it onto the stack and popping it off again takes O(n2) elementary operations, so that the total number of operations performed is O(n2) multiplied by the number of graphs the algorithm has to treat. The branching tree for this algorithm is a binary tree whose nodes are the graphs H the algorithm has to treat, with G as its root and the complete graphs as its leaves, and each internal node H for which the nonadjacent vertices x and y have been found has H+{x,y} and H(x=y) as its children. Each time the algorithm treats a complete graph it increases C[m] by 1 for some m, 1≤m≤n, so that the number of complete graphs it treats is C[1] + C[2] + ... + C[n], (4) and since the total number of nodes of a binary tree is twice the number of its leaves minus 1, the total time complexity of the algorithm is O(n2 multiplied by the sum in (4)). The worst case of this algorithm clearly occurs when G has no edges. In this case P(G,t)=tn. Substituting this value of P(G,t) into (3) we find that for each value of k, C[k]=S(n,k), a Stirling number of the second kind [4, p. 33]. Substituting these values into (4) we obtain the Bell number B(n). The worstcase time-complexity of this algorithm is thus O(n2B(n)). There is an asymptotic estimate for B(n) in [2]: B(n) ~ (R+1)-1/2exp[n(R+R-1-1)-1], (5)
44916266
Inversion of Cycle Index Sum Relations for 2- and 3-Connected Graphs
Abstract Algebraic inversion of cycle index sum relations is employed to derive new algorithms for counting unlabeled 2-connected graphs, homeomorphically irreducible 2-connected graphs, and 3-connected graphs. The new algorithms are significantly more efficient than earlier ones, both asymptotically and for modest values of the order. Tables of computed results are included.
18489826
Counting unrooted loopless planar maps
We present a formula for the number of n-edge unrooted loopless planar maps considered up to orientation-preserving isomorphism. The only sum contained in this formula is over the divisors of n.
43061363
Counting labelled three-connected and homeomorphically irreducible two-connected graphs
Abstract Recursive procedures are obtained for counting isomorphism classes of three-connected graphs and of two-connected graphs without vertices of degree 2. We apply an enumeration tool developed by R. W. Robinson to count non-isomorphic 2-connected graphs: he expressed the sums of cycle indices of automorphism groups of connected graphs in terms of those of their 2-connected components, and we do the same for 2-connected graphs and their 3-connected components.
14691140
Counting unlabelled three-connected and homeomorphically irreducible two-connected graphs
A graph will be assumed to be finite and unoriented, with no loops or multiple edges; if multiple edges are to be allowed, the term multigraph will be used. A graph or multigraph. will be called k-connected if at least k vertices and their incident edges must be removed to disconnect it (a complete graph is considered to be k-connected for any k). A block (respectively, multiblock) is a 2-connected graph (respectively, multigraph) with at least 2 vertices, and a brick is a 3-connected graph with at least 4 vertices. A Iabelling of a graph or multigraph with n vertices is a l-l correspondence from the set { 1, 2,..., n} onto the set of its vertices. Let A(x, y) be the mixed exponential generating function C,,, An,,,,x”.vmln!, where A,,, is the number of labelled graphs with n vertices and m edges, and let C(x, y) and B(x, y) be analogous generating functions which count labelled connected graphs and labelled blocks, respectively. The following formulae, due to Riddell [lo], appear in one-variable form in [6, pp. 3-111:
28528633
Total Vertex Enumeration in Rooted Planar Maps
1982428
Solving Non-clausal Formulas with DPLL search
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed using unrestricted propositional formulae and hence must be converted to CNF before modern SAT solvers can be applied. This conversion entails a considerable loss of information about the problem's structure. In this work we demonstrate that conversion to CNF is both unnecessary and undesirable. In particular, we demonstrate that a SAT solver which operates directly on a propositional formula can achieve the same efficiency as a highly optimized modern CNF solver. Furthermore, since the original formula remains intact, such a solver can exploit the original problem structure to improve over CNF solvers. We present empirical evidence showing that exploiting the original structure can yield considerable benefits. 
 
An extended abstract on this topic was presented at the SAT-2004 conference.
9791685
Symmetry Breaking
Symmetry occurs in many problems in aritifical intelligence. For example, in the n-queens problem, the chessboard can be rotated 90°. As a second example, several machines in a factory might have the same capacity. In a production schedule, we might therefore be able to swap the jobs on machines with the same capacity. As a third example, two people within a company might have the same skills. Given a staff roster, we might therefore be able to interchange these two people. And as a fourth example, when configuring a computer, two memory boards might be identical. We might therefore be able to swap them around without changing the performance of the computer.
38306882
Filtering Algorithms for the NValue Constraint
The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.
7228681
Tetravex is NP-complete
TETRAVEX is a widely played one person computer game in which you are given n2 unit tiles, each edge of which is labelled with a number. The objective is to place each tile within a n by n square such that all neighbouring edges are labelled with an identical number. Unfortunately, playing TETRAVEX is computationally hard. More precisely, we prove that deciding if there is a tiling of the TETRAVEX board given n2 unit tiles is NP-complete. Deciding where to place the tiles is therefore NP-hard. This may help to explain why TETRAVEX is a good puzzle. This result compliments a number of similar results for one person games involving tiling. For example, NP-completeness results have been show for: the offline version of Tetris [1], KPlumber (which involves rotating tiles containing drawings of pipes to make a connected network) [2], and shortest sliding puzzle problems [3]. It raises a number of open questions. For example, is the infinite version Turing-complete? How do we generate TETRAVEX problems which are truly puzzling as random NP-complete problems are often surprising easy to solve? Can we observe phase transition behaviour? What about the complexity of the problem when it is guaranteed to have an unique solution? How do we generate puzzles with unique solutions?
14685041
Propagating Logical Combinations of Constraints
Many constraint toolkits provide logical connectives like disjunction, negation and implication. These permit complex constraint expressions to be built from primitive constraints. However, the propagation of such complex constraint expressions is typically limited. We therefore present a simple and light weight method for propagating complex constraint expressions. We provide a precise characterization of when this method enforces generalized arc-consistency. In addition, we demonstrate that with our method many different global constraints can be easily implemented.