Some Branch and Bound Exercises



Graph Colouring:  Given a graph, colour the vertices such that no adjacent vertices have the same colour.  Use the smallest possible number of colours.

Maximal Satisfiability:  Given a Boolean expression in CNF, find a truth assignment to the literals that satisfies as many of the clauses as possible.

Integer Linear Programming:  Given an objective function f(x0, x1, ..., xn) and a set of linear constraints of the form  sum(ci * xi)  <= k, search the set of integer values for x0, x1, ..., xn that satisfy the constraints to find values that maximise f.

Longest Path:  Given a graph, find the longest path (sequence of edges that touches each vertex at most once)

Maximum Independent Set:  Given a graph, find the largest possible set S of vertices such that none of the vertices in S are adjacent to each other.

Maximum Clique:  Given a graph, find the largest possible set S of vertices such that all of the vertices in S are adjacent to each other (ok, if you've done the previous one this is pretty trivial!)


You may have noticed that a lot of these are optimization versions of classic NP-Complete problems.  Let's continue that theme.


Triangle Matching:  Given a graph, find the maximum number of DISJOINT vertex sets {a, b, c} such that within each set, all the vertices are adjacent.  By DISJOINT (which is naturally easier to understand because I am shouting), we mean that no vertex can belong to more than one of the sets.

Minimum Vertex Cover:  Given a graph, find the smallest possible set S of vertices such that every edge in the graph has at least one end in S.

Travelling Repairperson Problem:  Given a graph G with weighted edges and a start vertex s, find a traversal (not necessarily a path) of the graph that starts at s, visits each vertex at least once, and minimises the sum of the weights of the edges traversed before each vertex is reached for the first time.  (If this seems confusing, the story behind the problem title should help - imagine that a repairperson needs to fix a machine at each vertex, and the weights on the edges represent the time it takes to travel along the edges.  The waiting time for each vertex is the sum of the weights of all edges travelled before the vertex is reached for the first time.  We want to minimize the total waiting time).

Wandering Salesperson Problem:  Given a complete graph G with weighted edges with a start vertex s and a finishing vertex f, find a path that starts at s, finishes at f, visits every vertex exactly once, AND minimizes the largest edge weight used in the path.  (Again, a story may help - if the weights represent travelling time, then we want to minimize the longest time that the salesperson spends on the road between stops.)

Graph Partitioning:  Given a graph G and an integer k, partition the vertices of G into k sets such that the number of edges that have their ends in different sets is minimized.  This problem has applications to distributed computing.  If the vertices represent processes and the edges represent shared data, and we have k processors in the network, then we may want to assign processes to processors in such a way that every processor is busy, and the sharing of data between processors is minimized.