### OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION

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

## September, 1998

1. 2-INTERSECTION NUMBER [Jacobson, 1992]

INSTANCE: A path Pn = (V,E) with n vertices, a positive integer K.
QUESTION: Is the 2-intersection number of Pn <= K?

The idea here is to represent the path Pn with n vertices as an intersection graph. We associate with each vertex a subset of a given set A, where |A| = K, and we require that two vertices are adjacent if and only if the cardinality of the intersection of the corresponding two subsets >= 2. The 2-intersection number of a graph is the smallest cardinality of a set A on which a 2-intersection representation is possible. It is apparently extremely difficult to determine the 2-intersection number of a path! [M.S. Jacobson, A.E. Kezdy and D.B. West, The 2-Intersection Number of Paths and Bounded-Degree Trees, preprint].

2. NON-INTERSECTING LONGEST PATHS [Schwenk, 198X]

INSTANCE: A connected graph G = (V,E).
QUESTION: Does G have three longest paths which do not intersect in a common vertex?

Obviously, the problem of finding a longest path in a graph is NP-complete. This is not what Schwenk is asking. Instead, he wants to know if there exists a graph having three longest paths which do not intersect in a common vertex. All graph theorists know the famous result which states that every two longest paths in a connected graph must have a vertex in common. However, Schwenk says that a graph is known in which there exist something like seven longest paths which do not intersect in a common vertex. But no one has ever found a graph with three longest paths having this non-intersecting property.

3. TREE PACKING [Gyarfas and Lehel, 1974]

INSTANCE: A set of n-1 trees, T1,T2,...,Tn-1, where tree Ti has i edges.
QUESTION: Can this set of trees be packed exactly into Kn?

4. PLANAR DECOMPOSITION INTO SERIES-PARALLEL GRAPHS [Richey, 198X]

INSTANCE: A planar graph G = (V,E).
QUESTION: Can the edges of G be partitioned into two sets E1 and E2, each of which induces a series-parallel graph?

5. PLANAR DECOMPOSITION INTO OUTERPLANAR GRAPHS [Hedetniemi, 1968]

INSTANCE: A planar graph G = (V,E).
QUESTION: Can the edges of G be partitioned into two sets E1 and E2, each of which induces an outerplanar graph?

6. GRAPH RECONSTRUCTION [Folklore]

INSTANCE: A set of (vertex deleted) graphs of order n, G1, ... , Gn.
QUESTION: Does there exist a (unique) graph G whose vertex deleted subgraphs equal the given set of graphs?