7417163
Easy Problems are Sometimes Hard
We present a detailed experimental investigation of the easy-hard-easy phase transition for randomly generated instances of satisfiability problems. Problems in the hard part of the phase transition have been extensively used for benchmarking satisfiability algorithms. This study demonstrates that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classes and regions of the phase transition considered hard. These difficult problems are either hard unsatisfiable problems or are satisfiable problems which give a hard unsatisfiable subproblem following a wrong split. Whilst these hard unsatisfiable problems may have short proofs, these appear to be difficult to find, and other proofs are long and hard.
1199086
An Empirical Analysis of Search in GSAT
We describe an extensive study of search in GSAT, an approximation procedure for propositional satisfiability. GSAT performs greedy hill-climbing on the number of satisfied clauses in a truth assignment. Our experiments provide a more complete picture of GSAT's search than previous accounts. We describe in detail the two phases of search: rapid hill-climbing followed by a long plateau search. We demonstrate that when applied to randomly generated 3-SAT problems, there is a very simple scaling with problem size for both the mean number of satisfied clauses and the mean branching rate. Our results allow us to make detailed numerical conjectures about the length of the hill-climbing phase, the average gradient of this phase, and to conjecture that both the average score and average branching rate decay exponentially during plateau search. We end by showing how these results can be used to direct future theoretical analysis. This work provides a case study of how computer experiments can be used to improve understanding of the theoretical properties of algorithms.
17485829
Beyond Finite Domains: The All Different and Global Cardinality Constraints
We describe how the propagator for the ALL-DIFFERENT constraint can be generalized to prune variables whose domains are not just simple finite integer domains. We show, for example, how it can be used to propagate set, multiset and tuple variables.
2156641
Multiset Ordering Constraints
We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement a linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. Experimental results show considerable promise.
11070611
The Constrainedness of Arc Consistency
We show that the same methodology used to study phase transition behaviour in NP-complete problems works with a polynomial problem class: establishing arc consistency. A general measure of the constrainedness of an ensemble of problems, used to locate phase transitions in random NP-complete problems, predicts the location of a phase transition in establishing arc consistency. A complexity peak for the AC3 algorithm is associated with this transition. Finite size scaling models both the scaling of this transition and the computational cost. On problems at the phase transition, this model of computational cost agrees with the theoretical worst case. As with NP-complete problems, constrainedness — and proxies for it which are cheaper to compute — can be used as a heuristic for reducing the number of checks needed to establish arc consistency in AC3. 
 
The authors are supported by EPSRC awards GR/L/24014 and GR/K/65706, and the EU award EU20603. The authors wish to thank other members of the APES research group for their help, and Gene Freuder.
8350620
The Use of Proof Plans to Sum Series
We describe a program for finding closed form solutions to finite sums. The program was built to test the applicability of the proof planning search control technique in a domain of mathematics outwith induction. This experiment was successful. The series summing program extends previous work in this area and was built in a short time just by providing new series summing methods to our existing inductive theorem proving system CLAM.
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:
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)
1960492
Challenges in securing voice over IP
Although VoIP offers lower cost and greater flexibility, it can also introduce significant risks and vulnerabilities. This article explains the challenges of VoIP security and outlines steps for helping to secure an organization's VoIP network.
28528633
Total Vertex Enumeration in Rooted Planar Maps
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.