### OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION

compiled by
Steve Hedetniemi
Department of Computer Science
Clemson University
Clemson, SC 29634-1906

## September, 1998

1. CYCLES IN N-CONNECTED GRAPHS [Hedetniemi, 1993]

INSTANCE: An n-connected graph G = (V,E), a set S of n>2 vertices.
QUESTION: Can you construct in polynomial time a cycle containing all of the vertices in S?

It is known that such a cycle always exists. For n=2 such a cycle can be constructed in polynomial time.

2. GRID TSP [Hedetniemi, 1993]

INSTANCE: An edge-weighted, complete M x N grid graph G = (V,E), and a positive integer K.
QUESTION: Does there exist a Hamiltonian cycle in G of weight <= K?

3. DISJOINT CYCLES [Posa, 1963]

INSTANCE: A graph G = (V,E) with n vertices and >= 3n-5 edges.
QUESTION: Does G contain two disjoint cycles?

The answer to this question is always, yes, due to a theorem of Posa. My question is: can you find two disjoint cycles in such a graph in polynomial time? [L. Posa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl., 8 (1963), 355-361]

4. HAMILTONIAN CYCLE IN RANDOM CUBIC GRAPHS [Wormald and Robinson, 19XX]

INSTANCE: A random, cubic graph G = (V,E).
QUESTION: Does G contain a Hamiltonian cycle?

Robinson and Wormald have proved that almost all random, cubic graphs are Hamiltonian. My question is: given a random, cubic graph can you find such a Hamiltonian cycle in polynomial time? Bollobas, when asked about the difficulty of computing a typical optimization parameter of a random graph, speculated that most, if not all, NP-complete problems have linear solutions when restricted to random graphs. Thus, using the Bollobas 'thesis', it should be easy to find a Hamiltonian cycle in a random, cubic graph.

5. HAMILTON CYCLE IN CAYLEY GRAPH

INSTANCE: A Cayley graph G = (V,E).
QUESTION: Does G contain a Hamiltonian cycle?

A Cayley graph G(X) is obtained from an arbitrary group G and a finite set X of generators for G. The vertices of G(X) correspond 1-1 with the vertices of G, and two vertices u and v are adjacent in G(X) if and only if the equation ux = v holds for some generator x in X. It has long been conjectured that every Cayley graph is Hamiltonian.

6. HAMILTONIAN CYCLE IN 4-REGULAR PRISM GRAPHS [Rosenfeld, 198X]

INSTANCE: A 4-regular prism graph G = (V,E).
QUESTION: Does G contain a Hamiltonian cycle?

Let G be an arbitrary cubic graph and let G' be a copy of G. The prism graph on G is formed by adding edges between each vertex v in G and its isomorphic copy v' in G'. According to Rosenfeld it is not known whether every such 4-regular prism graph is Hamiltonian.

7. RANDOM HAMILTONIAN TREE WALK [Wilf, 198X]

INSTANCE: A rooted tree T = (V,E,r) with |V| = n vertices.
QUESTION: What is the expected length of a random Hamiltonian walk in T, starting at the root r?

The object here is to start a random walk at vertex r and keep walking until all vertices have been visited at least once (it isn't necessary to return to the starting vertex). Having arrived at a given vertex v, the next vertex visited is chosen among its neighbors with equal probability. Wilf says that the expected length of such a walk is no greater than O(n3). The expected length is known for paths and cycles and a few other classes of graphs.

8. EXCHANGE MINIMUM TSP [Tovey, 198X]

INSTANCE: An edge-weighted complete graph G = (V,E),
QUESTION: How difficult is it to find a Hamiltonian circuit whose weight cannot be lowered by an exchange of a pair of edges?

9. VERTEX TRANSITIVE HAMILTONIAN PATH [Lovasz, 198X]

INSTANCE: A vertex transitive graph G = (V,E).
QUESTION: Does G have a Hamiltonian path?

Actually, Lovasz asks, does every vertex transitive graph have a Hamiltonian path?

10. DOUBLE CYCLE [Johnson, 19XX]

INSTANCE: A graph G = (V,E) which is bridgeless.
QUESTION: Does there exist a family C of cycles of G (not necessarily distinct) such that each edge of G appears in exactly two cycles of C?

11. CHORD REALIZABLE GRAPH [Rosenfeld, 198X]

INSTANCE: A set of n positive integers {l1, l2, ... , ln}, such that each li >= 3.
QUESTION: Does there exist a Hamiltonian cubic graph G on 2n vertices whose short chord lengths are {l1,l2,...,ln}?

Let v1, v2, ... , v2n be the vertices, in order, of a cycle C. If we add an arbitrary chord to C, say between vertices vi and vj, then the short chord length of this chord is the minimum distance between vi and vj in C.

12. CYCLE REALIZABLE GRAPH [Jacobson, 1993]

INSTANCE: An n-tuple A[1..n] of 0's and 1's.
QUESTION: Does there exist a graph G = (V,E) with n vertices such that G has a cycle of length i, 3 <= i <= n if and only if A(i) = 1 {we assume that A = A = 0}.