INSTANCE: A rooted tree T = (V,E,r).

QUESTION: Is T a union/find tree?

Can you construct an algorithm for deciding if an arbitrary tree T is a union/find tree? Union/find trees can be defined recursively as follows: (i) a rooted tree with a single vertex is a union/find tree; (ii) if T' and T'' are union/find trees, with roots r' and r'', respectively, and if T' has at least as many vertices as T'', then the tree T rooted at vertex r' which is formed from T' and T'' by adding an edge between r' and r'' is a union/find tree; (iii) if T is a union/find tree with root r and v is any vertex in T, then the tree obtained from T by deleting every edge on the unique path between r and v and adding a new edge between r and each vertex on this path is a union/find tree. (iv) nothing is a union/find tree unless its being so follows from a finite number of applications of rules (i), (ii) and (iii).

Leizhen Cai has characterized union trees [Inform. Process. Lett. 45(3)(1993) 279-283], i.e. the trees formed by using only rules (i), (ii) and (iv). This result was also independently obtained both by S.M. Hedetniemi and by C. Wallis, circa 1991.

INSTANCE: An edge-weighted complete graph G, a positive integer K.

QUESTION: Does G have a spanning subgraph of Type i and weight <= K?

Given an edge-weighted complete graph G = (V,E), can you construct a polynomial algorithm for finding a minimum weight spanning subgraph G' which is of the following type?

1. G' is a 2-tree [Lubiw]

2. G' is a spider [Hedetniemi]

3. G' is a binary tree [Hedetniemi]

4. G' is a caterpillar [Hedetniemi]

5. G' is a 2-regular graph [Hedetniemi]

INSTANCE: A tree T = (V,E), and a positive integer K.

QUESTION: Is there a non-empty collection C' of closed neighborhoods N[v] of T, with |C'| <= K, such that each vertex v in V is in an even number (possibly zero) of neighborhoods of C'?

Although it has been shown that every graph G has an ODD NEIGHBORHOOD COVER, not every graph has an EVEN NEIGHBORHOOD COVER. Dawes has constructed a polynomial algorithm for deciding if an arbitrary tree T has an ODD NEIGHBORHOOD COVER of size <= K [19XX].

INSTANCE: Two trees T = (V,E) and T' = (V',E') and a subset R of V x V .

QUESTION: Is there an isomorphism f between T and T' such that, when viewed as a set of ordered pairs, f contains no pair from R?

For arbitrary graphs G and G' this problem is NP-complete, but what about trees?

INSTANCE: A tree T = (V,E) from a given family.

QUESTION: Is there a partition {E₁,E₂} of E such that the two forests T₁ = (V,E₁) and T₂ = (V,E₂) are isomorphic?

For arbitrary trees T this problem is NP-complete [Graham and Robinson]. For paths, stars, spiders, binomial trees, Fibonacci trees and binary trees this question can be answered in polynomial time [Wallis and Knisely 199X]. Is there a polynomial algorithm for answering this question for: (i) heaps or (ii) caterpillars?

INSTANCE: An array A[1..n] of positive integers.

QUESTION: Do there exist two permutations r and s of the positive integers {1,2, ... , n} such that for 1 <= i <= n, r(i) + s(i) = A[i]?

INSTANCE: A tree T = (V,E), a subset S of vertices and a positive integer K.

QUESTION: Does there exist a set S' of vertices of size <= K such that for every pair of vertices u,v in S, there exists a vertex w in S' for which u is in N[w] but v is not?

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Is the forwarding index of G <= K?

You seek a family of paths in a graph G such that every pair of vertices occurs on at least one path. In general, the union of these paths forms a multigraph. You want to minimize the maximum number of multiple edges connecting any pair of adjacent vertices. The minimum value of this maximum number of multiple edges, over all families of paths whose union contains all pairs of vertices, is called the forwarding index of G. It is obvious that this problem is NP-Hard, since the forwarding index of a graph G equals one if and only if G has a Hamiltonian path. Can you construct an algorithm for determining the forwarding index of any class of graphs (other than trees, for which the problem is simple)?

INSTANCE: An graph G = (V,E), a positive integer K.

QUESTION: Does G contain a spanning tree T, having a centroid vertex v whose transmission number is <= K?

The transmission number of a vertex v in a graph G is the sum of d(v,w), over all vertices w in V.

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Does G have a strong matching set of vertices of size > =K?

The strong matching number of a graph G is the maximum number of edges in a set M such that the subgraph induced by V(M), the set of vertices contained in the edges in M, consists of disjoint copies of K₂. Laskar and Golumbic have constructed a linear algorithm for computing the strong matching number of any tree and any circular arc graph. They also showed that this problem is NP-complete for arbitrary graphs. I know of no other strong matching algorithm. [K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102] [M.C. Golumbic and R.C. Laskar, Irredundancy in circular arc graphs, Discrete Appl. Math. 44 (1993) 79-89]

INSTANCE: A tree T=(V,E), positive integers a₁₂, a₂₃, a₁₃ such that a₁₂ + a₂₃ + a₁₃ = |E|.

QUESTION: Does there exist a homomorphism from T onto the complete graph with three vertices, labelled 1,2 and 3, such that a₁₂ edges of T are mapped to the edge (1,2), a₂₃ edges of T are mapped to the edge (2,3) and a₁₃ edges of T are mapped to the edge (1,3)?

A homomorphism from a graph G=(V,E) to a graph G' = (V',E') is a function f: V --> V' such that for all vertices u and v, if u is adjacent to v then f(u) is adjacent to f(v).

a. INSTANCE: A 4-connected planar graph G = (V,E).

QUESTION: Does G contain a spanning tree with maximum degree <= 2?

The answer to this question is always, YES. In 1956, Tutte proved that every 4-connected planar graph is Hamiltonian. In 1984 Asano, Kikuchi and Saito constructed a linear algorithm for finding a Hamiltonian cycle in a 4-connected maximal planar graph. [T. Asano, S. Kikuchi and N. Saito, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Discrete Appl. Math. 7 (1984), 1-15]

b. INSTANCE: A 3-connected planar graph G = (V,E).

QUESTION: Does G contain a spanning tree with maximum degree <= 3?

Again, the answer to this question is yes, due to a theorem of Barnette. My question is can you construct such a spanning tree in polynomial time?

c. INSTANCE: A 2-connected planar graph G = (V,E).

QUESTION: Does G contain a spanning tree with maximum degree <= 4?

Here I have two questions: first, do the previous two theorems extrapolate to 2-connected planar graphs, and second, can you find such a spanning tree in polynomial time?

INSTANCE: A graph G = (V,E).

QUESTION: Does G contain a subdivision of K₅, the complete graph on five vertices?

This is related to an old conjecture:

CONJECTURE [Dirac]. Any graph having n vertices and at least 3n-6 edges contains a subdivision of K₅.

My question is, even if you can be guaranteed that a graph has a subdivision of K₅, say because it has enough edges, can you find one in polynomial time?

INSTANCE: A real-valued n x n matrix A, a positive integer K.

QUESTION: How many of the entries of A need to be examined, in the worst case, in order to decide whether A has a saddle point?

A saddle point is an entry which is a maximum in its row and a minimum in its column. Tovey claims that no more than n^{log 3} entries need to be examined.

INSTANCE: A rooted tree T = (V,E,r), positive integers K and V.

QUESTION: Does there exist a set of K walks, each beginning at vertex r, which collectively contain every vertex in T, and which has a weighted sum <= V?

This is a variant of a recent problem posed by Hedetniemi and solved by Robert Reynolds. Given a rooted tree T, you seek a walk beginning at the root of T, which includes every vertex in T and which has a minimum weighted sum. The weighted sum of a walk W is defined as follows: for each vertex v in T determine the first time v occurs in W and let val(v) equal the length of the walk from the root to this first occurrence of v. The sum of all values val(v) for all vertices in T is the weighted sum of walk W, also referred to as the minimum latency of W. Reynolds' theorem is that the minimum latency of any walk in a tree T, which begins at the root and contains every vertex, is obtained by any depth-first search of T. This variant allows K different walks.

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Does G contain a spanning tree of diameter <= K?

This problem is shown to be NP-completen Garey and Johnson's book. However, I do not recall seeing any algorithm for solving this problem on any restricted family of graphs.

INSTANCE: A graph G = (V,E).

QUESTION: Is G perfect? i.e. does either G or its complement contain an induced odd cycle?

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Is the crossing number of G <= K? i.e. can G be embedded in the plane in such a way that no more than K edges cross?

INSTANCE: A connected graph F = (V',E') or order n > 2.

QUESTION: Does there exist a graph G = (V,E) such that each vertex v in V belongs to a different number of copies of F in G?

INSTANCE: Two graphs G = (V,E) and G' = (V',E') with |V| = |V'| and |E| = |E'|, a positive integer K.

QUESTION: Is there a sequence of <= K rotations of edges of G which transforms G into G'?

A rotation of an edge uv consists of pivoting it at one end, say u, and rotating the other end to another vertex w. Thus it is equivalant to removing the edge uv and replacing it with either uw or vw for some vertex w. Thus, with two rotations, we can, in effect, move any edge uv to any other pair of vertices wx. Note that if G and G' are isomorphic, then K = 0 rotations suffice to transform G to G'. This suggests the next, famous open problem. [L.E. Clarke, On Cayley's formula for counting trees, J. London Math. Soc. 33 (1958), 471-474.] [R.J. Faudree, R.H. Schelp, L. Lesniak, A. Gyarfas and J. Lehel, On the rotation distance of graphs, submitted to Discrete Math.]

INSTANCE: Two graphs G1 = (V1,E1) and G2 = (V2,E2).

QUESTION: Are G1 and G2 isomorphic, i.e. is there a ono-to-one f: V1 --> V2 such that uv is in E1 if and only if f(u)f(v) is in E2?

INSTANCE: A graph G = (V,E).

QUESTION: Is G quadratic?

A graph G is quadratic if the edges of G can be covered by complete bipartite graphs Km,n in such a way that no vertex belongs to more than two Km,n's.

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Does G contain a maximal induced path of length <= K?

The similar problem, called INDUCED PATH in Garey and Johnson, where one asks if G contains an induced path of length >= K, is NP-complete.