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.
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?
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].
For arbitrary graphs G and G' this problem is NP-complete, but what about trees?
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?
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)?
The transmission number of a vertex v in a graph G is the sum of d(v,w), over all vertices w in V.
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 K2. 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]
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).
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]
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?
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?
This is related to an old conjecture:
CONJECTURE [Dirac]. Any graph having n vertices and at least 3n-6 edges contains a subdivision of K5.
My question is, even if you can be guaranteed that a graph has a subdivision of K5, say because it has enough edges, can you find one in polynomial time?
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 nlog 3 entries need to be examined.
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.
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.
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.]
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.
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.