Number: 1
Name: 3-Satisfiability (3-SAT) [LO2] 2
Input: A set of m clauses - C1,C2,...,Cm - over a set of n Boolean valued variables Xn = < x1,x2,...,xn>, such that each clause depends on exactly three distinct variables from Xn.
Comments: One of the key problems in the study of phase-transition effects in back-tracking procedures. Instances of this problem with `less' than about 4n clauses (where n is the number of variables, appear to allow satisfying assignments to be found quickly. A good reference for work on this problem is the material in the special issue (Vol 81) of Artificial Intelligence that was mentioned in the earlier document.
Name: Graph 3-Colourability (3-COL) [GT4] 1
Input: An n-node undirected graph G(V,E) with node set V and edge set E.
Comments: Another problem that is important in work on phase-transitions: graphs with less than about 2n edges appear to be `easier' to find 3-colourings for, when employing an appropriate back-tracking search method. Similarly graphs with more than about 2.5n edges seem to be `easier' to refute the existence of a 3-colouring in. The paper,
Paul E. Dunne and Michele Zito:
An improved upper bound on the non-3-colourability threshold,
Information Processing Letters, 65 (1), February 1998, pp 17-23,
is available is the Library (a copy will be temporarily available, located here), presents a (very complicated) description of how the 2.5n bound is obtained. This problem is, also, one of a small number of problems that remains NP-complete, even when restricted to planar graphs.
Name: Monochromatic triangle [GT6] 2
Input: An n-node undirected graph G(V,E) with node set V and edge set E.
Comments: The nature of the property with which this problem is concerned suggests that, once again, it may be possible to exploit phase-transition effects, but I'm not aware of any results of this kind. Similarly, I'm unaware of the status of `non-trivial' special cases, e.g. planar graphs.
Name: Clique [GT19] 1
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k <= n.
Comments: If one treats this as an optimisation problem, i.e determine the number of nodes in the largest clique contained in G, there has been some study of `greedy-type' algorithms. It is known that solving the optimisation problem to within some constant factor, i.e. guaranteeing to deliver a clique of size at least c k(G), where k(G) is the size of the maximum clique and c > 0 is a constant, is as hard as solving the strict decision problem form above. As regards special cases: planar graphs are trivial (maximum size of a clique in any planar graph is 4); as are cases where the maximum degree of the graph is bounded by a constant; similarly the famous theorem of Turan provides an easily tested condition that guarantees the presence of a clique of a certain size.
Name: Bipartite Subgraph [GT25] 2
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k <= |E|.
Comments: Can be viewed as an optimisation problem (maximisation).
Name: Vertex Cover [GT1] 1
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k <= n.
Comments: Can be treated as a minimisation problem.
Name: Chromatic Index (Edge Colouring) [OPEN5] 3
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k<=|E|.
Comments: The paper by Gibbons and Ogunyode (1985), mentioned in the previous assignment notes, provides an example of an algorithm which is `usually' fast and constructs an appropriate edge-colouring. Recent work has been carried out, concerning graphs in which every node has the same constant degree - so-called k-regular or k-valent graphs - a class to which the methods of Gibbons and Ogunyode cannot be applied. This work, by Wormald, Jerrum et al., yields similar algorithms. I haven't seen these papers so I have no idea how involved the methods are.
Name: Multiprocessor Scheduling [SS8] 4
Input: A set, T, of tasks and for each task t in T a positive (integer) running time len(t). A positive integer D, called the deadline.
Comments: Ideal greedy approach problem: a technique which, I believe, has been studied in this context.
Name: Comparative Divisibility [AN4] 3
Input: A (strictly increasing) sequence A= < a1,a2,...,an> and a (strictly increasing) sequence B=< b1,...,bm> of positive integers.
Comments: Apart from trivial special-cases, there isn't really that much room (that I'm aware of) for this kind of number-theoretic problem. There may be some tricks that use some deep number-theoretic results, otherwise ....
Name: Cyclic Ordering [MS2] 3
Input: A finite set, A, and a collection, C, of ordered triples (a,b,c) of distinct elements from A.
Comments: The fact that the larger the number of triples in C the less likely there is to be a solution, indicates that this problem might well be one that can be solved quickly by a back-tracking search method when there are either `few' triples in C or a `large' number of such triples, i.e. this is a plausible candidate for exploiting phase-transition ideas.
Name: Quadratic Diophantine Equations [AN8] 3
Input: Positive integers a, b, and c.
Comments: Not a great deal of scope for doing anything with this: a difficulty with most number-theoretic problems unless there are some clever techniques that I don't know much about(!)
Name: Maximum 2-Satisfiability [LO5] 3
Input: A set of m clauses C1,C2,...,Cm over n Boolean valued variables Xn, where each clause depends on two distinct variables from Xn; a positive integer k with k<= m.
Comments: Optimisation problem (maximisation). Quite a lot of scope for trying different techniques, although this is recognised as a problem that is hard even to get good approximation schemes for.
Name: Register Sufficiency [PO1] 5
Input: A directed, acyclic graph G(V,A) in which each node has at most two out-going edges; a positive integer k.
Comments: A minimisation problem. Particular graph structures might be capable of allowing exact solutions. Greedy methods may also be worth examining.
Name: Central Slice of Half-Clique 2
Input: An 2n-node undirected graph G(V,E) with node set V and edge set E.
Comments: Sorry, you'll just have to devise an exhaustive search method for this one. The problem is very tightly constrained which doesn't leave any room to manipulate things. It might be possible to look for some clever searching tricks, but I suspect these won't buy anything in the final analysis.
Name: Decision Tree [MS15] 5
Input: A Boolean logic function, f, of n variables, Xn, described by its 1-points, i.e. the set of assignments, alpha=< a1,...,an> such that f(a1,...,an)=1; a positive integer K.
Comments: A lot of special cases with exact solutions (e.g. threshold functions as in the paper by Dunne and Leng mentioned in the previous commentary); and considerable scope for heuristic techniques, greedy approximation methods etc. Or you could try and do it exhaustively.
Name: Shortest Common Superstring [SR9] 3
Input: A finite set R={r1,r2,...,rm} of binary strings (sequences of 0 and 1); positive integer k.
Comments: Effectively an optimisation problem (minimisation). Naive (and worthless solution, in terms of algorithmic interest) is just to concatenate the m strings in R together. There may be some nice approaches based on taking pairs of of strings and trying to attach a value to these in terms of number of bits overlapping. I have no idea how this will perform in practice but there's a reasonable range of ideas to experiment with.
Name: Longest Circuit [ND28] 2
Input: n-node undirected graph G(V,E); positive integer k.
Question: Does G contain a simple cycle containing at least k nodes?
Comments: Optimisation problem (maximisation). May be some kind of greedy approach will give a solution, however, there is a reasonable body of literature available on approximation and heuristic techniques.
Name: Kernel [GT57] 2
Input: n-node directed graph G(V,A).
Comments: I don't know that much can be done with this. It looks like a problem where the best one can achieve is to try and find reasonable exhaustive search approach, i.e. back-tracking method. I don't know of any non-trivial classes of graphs for which the problem can be solved quickly.
Name: k-Closure [GT58] 2
Input: n-node directed graph G(V,A); positive integer k<= n.
Comments: Optimisation problem. (Minimisation) Again, I don't know of any non-trivial classes of graphs for which the problem can be solved quickly.
Name: Bandwidth [GT40] 3
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Optimisation problem. (Minimisation) No reasonable (to within a constant factor) approximation methods are known. Also, one of the very rare examples of NP-complete graph problems that remain NP-complete when restricted to trees, (even binary trees).
Name: Maximum Leaf Spanning Tree [ND2] 4
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Optimisation problem (maximisation), and one for which good approximation techniques exist, although the algorithms are non-trivial. Remains NP-complete even for k-valent graphs (those in which every node is the end-point of exactly k edges), although one can prove some performance bounds in this case, cf the paper Dunne (1987) referred to previously which does so in a manner that yields an algorithm achieving these bounds. If you're going to try implementing this .... well, you know my e-mail address.
Name: Independent Set [GT20] 1
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Optimisation problem (maximisation). Equivalent to Clique (Problem 2), the comments made with respect to this problem, therefore being equally applicable to Independent Set.
Name: Degree Constrained Spanning Tree [ND1] 4
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Can be treated as an optimisation problem (minimisation) in which the objective function is the degree of the spanning tree. I don't know about special cases, although for k=2, since this corresponds to Hamiltonian Path, any special case for which Hamiltonian Path can be solved, will also deal with this case. Possible greedy approach through ordering nodes on degree, but I don't know how this performs in practice.
Name: Hamiltonian Path [GT39] 1
Input: n-node undirected graph G(V,E).
Comments: Still remains NP-complete if the graph is planar. Doesn't seem like there's a lot of choice here other than clever exhaustive search, although this is a problem where phase-transition ideas may lead to some cases being quickly solvable by such methods.
Name: Graph Partitioning [ND14] 2
Input: 2n-node undirected graph G(V,E); positive integer k<=|E|.
Comments: Optimisation problem (minimisation). The heuristic of Kernighan and Lin was mentioned previously. Easily solved for trees. There is a clever technique (whose implementation is non-trivial) that performs well on planar graphs arising from a classic paper of Tarjan and Lipton that dates from 1978. In a similar vein, there has been a considerable study of this problem for classes of graphs that are `related to' processor interconnection schemes arising in parallel computer architectures, e.g. hypercubes, meshes, etc.
Name: Cubic Subgraph [GT32] 3
Input: n-node undirected graph G(V,E).
Comments: Probably exhaustive search is the only way that this will be solvable in general. Note, however, that this is another problem that `extreme' cases (graphs with a `few' edges; graphs with a `lot' of edges) may be resolved quickly by a good method. An interesting result in this context is by Erdös and Simonovits from 1973, namely that every n node graph with at least n5/3 edges has a cubic subgraph (I'm considerably simplifying the statement of this result). This gives a simple immediate check that can be made on the input.
Name: Travelling Salesman [ND22] 3-4
Input: A set C of n cities {c1,...,cn; for each pair of cities (ci,cj) (1<= i < j <= n) a positive integer distance di,j; a positive integer B.
Comments: Optimisation problem (minimisation). As stated before, a lot of literature and research carried out on this problem concerning approximation and heuristic techniques.
Name: Steiner Tree in Bipartite Graphs [ND12a] 3
Input: Bipartite graph B(V,W,E); positive integer k.
Comments: Optimisation problem (minimisation).
Name: Bounded Diameter Spanning Tree [ND4] 4
Input: n-node undirected graph G(V,E); for each edge, {u,v} a positive integer weight w(u,v); positive integer B.
Comments: Optimisation problem (minimisation). Rather more difficult, given the additional condition on solution requirements, i.e. not just minimum weight but minimum weight subject to ...
Name: Optimal Linear Arrangement [GT42] 3
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Optimisation problem (minimisation) that is superficially similar to Bandwidth (Problem 20) and to which all of the remarks concerning Bandwidth apply (and then some).
Name: Dominating Set [GT2] 2
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Optimisation problem (minimisation). Remains NP-complete for planar graphs, but the (very limited) case of trees can be solved exactly by efficient methods. This algorithm is non-trivial.
Name: Path with Forbidden Pairs [GT54] 4
Input: n-node directed graph G(V,A); two distinct nodes s and t belonging to V; finite collection C={(a1,b1),...,(ar,br)} of pairs of nodes from V.
Comments: Several special cases remain NP-complete: requiring G to be acyclic; requiring the collection C to contain only directed edges from A (rather than arbitrary pairs of nodes); requiring all the pairs to be disjoint. Structure of problem indicates that extreme cases may perform well using exhaustive back-tracking search.
Name: Oriented Diameter [GT64] 4
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Optimisation problem (minimisation). Of the two specified conditions for a solution, only the second needs to be tested (it implies the first).
Name: Rural Postman [ND27] 3-4
Input: n-node undirected graph G(V,E); subset F of the edges E; positive integer k<=|E|
Comments: Optimisation problem (minimisation). I don't know of any non-trivial special cases.
Name: Longest Path [ND29] 2
Input: n-node undirected graph G(V,E); nodes s and t in V; positive integer k.
Comments: optimisation problem (maximisation). There is an efficient algorithm for the special case of directed acyclic graphs.
Name: 3-Dimensional Matching (3DM) [SP1] 3
Input: 3 disjoint sets X, Y, and Z each comprising exactly n elements; a set M of m triples {(xi,yi,zi):1 <= i <= m} such that xi is in X, yi in Y, and zi in Z, i.e. M is a subset of XxYxZ.
Comments: Almost certainly another NP-complete problem which can be resolved quickly by exhaustive search for `extreme' cases.
Name: Set Splitting [SP4] 3
Input: A finite set S; A collection C1,...,Cm of subsets of S.
Comments: Similar remarks to Problem 36 apply.
Name: Set Packing [SP3] 3
Input: A collection C=(C1,...,Cm) of finite sets; a positive integer k <= m.
Comments: Optimisation problem (maximisation).
Name: Exact Cover by 3-Sets (X3C) [SP2] 3
Input: A finite set X containing exactly 3n elements; a collection C of subsets of X each of which contains exactly 3 elements.
Comments Fast algorithm for the special case where no element of X occurs in more than two of the sets in C.
Name: Minimum Cover [SP5] 3-4
Input: A finite set S; A collection C=(C1,...,Cm) of subsets of S; a positive integer k<= m.
Comments: Optimisation problem (minimisation).
Name: Partition [SP12] 3
Input: Finite set A; for each element a in A a positive integer size s(a).
Comments: This can be viewed as a minimisation problem, in which the objective
function is
| sum over x in A1 s(x) -sum over y in A2 s(y) |.
| ... | denoting `absolute value'.
Name: Subset Sum [SP13] 3
Input: Finite set A; for each element a in A a positive integer size s(a); a positive integer K.
Comments: Similarly to Problem 41, can be treated as an optimisation problem in which the objective function is |K- sum from {x inB} s(x)|.
Name: Comparative Containment [SP10] 4
Input: A finite set X; 2 collections R=(R1,...,Rk) and S=(S1,...,Sm) each of which is a set of subsets of X; for each Ri in R, a positive integer weight w(Ri); for each Si in S a positive integer weight w(Si);
Comments: Looks like an exhaustive search case.
Name: Minimum Test Set [SP6] 3
Input: A finite set S; A collection C=(C1,...,Cm) of subsets of S; a positive integer k <= m.
Comments: Optimisation problem (minimisation)
Name: Minimum Sum of Squares [SP19] 3-4
Input: A set A of n elements; for each element a in A a positive integer size s(a); positive integers k<= n and J.
Comments: Optimisation problem. (minimisation).
Name: 3-Partition [SP15] 3
Input: A set A of 3m elements; a positive integer bound B; for each element x in A a positive integer size s(x) that satisfies B/4 < s(x) < B/2, and is such that the sum of the sizes of elements in A is exactly mB.
Comments: There are some short-cuts, but basically looks like an exhaustive search required.
Name: Subset Product [SP14] 3
Input: Finite set A; for each element a in A a positive integer size s(a); a positive integer K.
Comments: Could be treated as a minimisation problem using the same device employed in Problems 41 and 42.
Name: Bin Packing [SR1] 3
Input: A finite set U of m items; for each item u in U a positive integer size s(u); positive integers B (called the bin capacity) and k <= m.
Comments: Optimisation problem (minimising k). If B is constant then exhaustive search is actually `efficient' (i.e. run-time is of the order tB for some t depending on input parameters.
Name: Hitting String [SR12] 3
Input: Finite set S={s1,...,sm} each si being a string s1is2i...sni of length n over {0,1,*}.
Comments: Organised exhaustive search `should' perform `well' when m is not `too large' (greater chance of appropriate x existing) or when m is `very large' (may be able to determine `quickly' that there is no suitable x).
Name: Rectilinear Picture Compression [SR25] 4-5
Input: An nXn matrix M of 0s and 1s; a positive integer K.
Comments: Optimisation problem (minimisation).
Name: Sequencing with Release Times and Deadlines [SS1] 4-5
Input: A set T of tasks; for each task t in T: a positive integer length len(t); a positive integer release time r(t); and a positive integer deadline d(t).
Comments: Can be treated as an optimisation problem in which the aim is to minimise the the time at which the last task is completed.
Name: Precedence Constrained Scheduling [SS9] 3-4
Input: A set T of tasks each of which has length 1 or length 2; a partial ordering << on the set of tasks, T; a positive integer deadline D.
Comments: Optimisation problem (minimising D).
Name: Quadratic Congruences [AN1] 3
Input: Positive integers a, b, and c.
Comments: Number-theoretic problem: comments made previously with respect to Problems 9 and 11 apply.
Name: Square-Tiling [GP13] 5
Input: A set C of n `colours'; a collection of tiles, T, each tile t being a 4-tuple < a,b,c,d > of colours where a is the colour at the top of the tile; b that on the right-hand side; c that at the bottom; and d that on the left-hand side of the tile; a positive integer k <= n.
Comments: Don't see any alternative to exhaustive searching for this.
Name: Crossword Puzzle Construction [GP14] 5
Input: A finite set of characters SIGMA={sigma1,...,sigmak}; a finite set, W={w1,...,w2n} each wi being a sequence of n characters from SIGMA, i.e. a string.
Comments: Or for this.
Name: Disjunctive non-tautology [LO8] 2
Input: A A set of m products - P1,P2,...,Pm - over a set of n Boolean valued variables Xn=< x1,x2,...,xn>, such that each product depends on exactly three distinct variables from Xn. A product being a Boolean expression of the form yiAND yj AND yk where each y is of the form x or not x (i.e. negation of x) with x being some variable in Xn.
Comments: Comments made with respect to Problem 1 all apply for this problem.
Name: Simultaneous incongruences [AN2] 3
Input: A set of n ordered pairs of positive integers {(a1,b1),...,(an,bn)} where ai<= bi for each 1 <= i <= n.
Comments: As with most number-theoretic problems, the comments regarding Problems 9, 11, and 53 apply.
Name: Betweenness [MS1] 3
Input: A finite set of size n, A; a set C of ordered triples, (a,b,c), of distinct elements from A.
Comments: Another problem where `extreme' cases (`very few' or `very many') triples should be resolvable quickly by back-tracking search.
Name: Minimum weight and/or graph solution [MS16] 4-5
Input: A directed acyclic graph G(V,A) having a single node s, with no incoming edges; a labelling, f(v) of each node having at least one out-going edge in G, as either an a nd-node or an or-node; a positive integer K.
Comments Optimisation problem (minimisation).
Name: Fault-detection in directed graphs. [MS18] 3-4
Input: A directed, acyclic graph G(V,A) such that G has a unique node t with no out-going edges; I the set of nodes in V having no incoming edges; a positive integer K.
Comments Optimisation problem (minimisation).
Name: Minimum Broadcast Time. [ND49] 3-4
Input: n-node undirected graph G(V,E); a subset V0 of the nodes in V.
Comments Optimisation problem (minimisation).
Name: Disjoint Connecting Paths [ND40] 3-4
Input: n-node undirected graph G(V,E); a set of disjoint pairs of nodes {(s1,t1);...;(sk,tk)}.
Comments: Optimisation problem (maximisation).
Name: Shortest Weight-Constrained Path [ND30] 3
Input: n-node undirected graph G(V,E); for each edge e in E a positive integer length len (e) and a positive integer weight w(e); specified nodes s and t in V; positive integers K and W.
Comments: Can be treated as a minimisation problem where the objective function depends on both path length and path weight (otherwise the problem is trivial). Obviously there are many choices as to how this could be done.
Name: Minimum Maximal Matching [GT10] 3
Input: n-node undirected graph G(V,E); positive integers k<=|E|.
Comments: Optimisation problem (minimisation).
Name: Partition into Triangles [GT11] 3
Input: (3n)-node undirected graph G(V,E).
Comments: Another example of a problem where careful back-tracking search may handle extreme cases well in general.
Name: Partition into Forests [GT14] 3
Input: n-node undirected graph G(V,E); positive integer k<= n
Comments: Can treat as an optimisation problem (minimisation), noting also that the comments regarding Problem 65 are also applicable.
Name: Partition into Cliques [GT15] 3
Input: n-node undirected graph G(V,E); positive integer k<= n
Comments: Similar to Problem 66.
Name: Partition into Perfect Matchings [GT16] 3
Input: n-node undirected graph G(V,E); positive integer k<= n
Comments: Similar to Problem 66.
Name: Covering by cliques [GT17] 3
Input: n-node undirected graph G(V,E); positive integer k<= n
Comments: Optimisation problem (minimisation).
Name: Degree-bounded connected subgraph [GT26] 3
Input: n-node undirected graph G(V,E); non-negative integer d<= n; positive integer k <= |E|.
Comments: An interesting example of a problem that can be treated as an optimisation problem in a number of ways: minimise (or maximise) some given function of the two parameters (degree and subgraph size); fix one and minimise/maximise the other (as appropriate).
Name: Uniconnected subgraph [GT30] 3
Input: n-node directed graph G(V,A); positive integer k <= |A|.
Comments: Optimisation problem (maximisation).
Name: Minimum k-connected subgraph [GT31] 3
Input: n-node undirected graph G(V,E); positive integers k<=n and B<=|E|.
Comments: Optimisation problem (fix k=2) minimising size of edge set removed.
Name: Minimum cut linear arrangement [GT44] 3
Input: n-node undirected graph G(V,E); positive integer k.
Comments: Optimisation problem (minimisation).
Name: Elimination degree sequence [GT47] 4
Input: n-node undirected graph G(V,E); a sequence < d1,d2,...,dn> of non-negative integers, all of which are at most n-1.
Comments: Looks like exhaustive search is only feasible option.
Name: Multiple choice matching [GT55] 3
Input: n-node undirected graph G(V,E); partition of E into t disjoint sets - E1,...,Et; positive integer k.
Comments: Optimisation problem (maximisation).
Name: Path distinguishers [GT60] 3
Input: n-node directed, acyclic graph G(V,A); specified nodes s and t in V; positive integer k <= |A|.
Comments: Optimisation problem (maximisation).
Name: Nestril-Rodl dimension [GT62] 5
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Either try exhaustive search, alternatively treat as an optimisation problem (maximisation) for which the objective function is the value of k.
Name: Shortest total path length spanning tree [ND3] 4-5
Input: n-node undirected graph G(V,E); positive integer B.
Comments: Minimisation problem.
Name: Induced Path [GT23] 3
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Maximisation problem.
Name: Bounded Component Spanning Forest [ND10] 3
Input: n-node undirected graph G(V,E); positive integer k<= n.
Comments: Minimisation problem.
Name: Maximum subgraph matching [GT50] 3
Input: Directed graphs G(V,A), H(W,B); positive integer k.
Comments: Maximisation problem.
Name: Numerical 3-dimensional matching [SP16] 3
Input: Disjoint sets W, X, and Y each containing exactly m elements; for each element u of W union X union Y, a positive integer size s(u); a positive integer bound B.
Comments: This could be treated as a minimisation problem, where the objective
function is
sum over i=1 to m |s(Ai)-B|
(s(Ai) being the total size of Ai
and | ... | denoting absolute value).
Name: Open Hemisphere [MP6] 4-5
Input: Finite set X of m-tuples of integers; a positive integer k<=|X|.
Comments: Exhaustive search looks like all that's available.
Name: Largest Common Subgraph [GT49] 3-4
Input: 2 n-node undirected graphs G(V,E), H(W,F); positive integer k.
Comments: Maximisation problem.
Name: Clustering [MS9] 3
Input: Finite set X; for each pair of elements x and y in X, a positive integer distance d(x,y); positive integer B.
Comments: Could be phrased as an optimisation problem (minimisation) in which the objective function is max d(x,y).