The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
Udi Manber, Martin Tompa · SIAM Journal on Computing · 1984
A generalization of Dobkin and Lipton’s element uniqueness problem is introduced. For any fixed undirected graph G on vertex set $\{ v _1 , v_2 , \cdots , v_n \} $, the problem is to determine, given n real numbers $x_1 ,x_2 , \cdots ,x_n $, whether $x_i e x_j $ for every edge $\{ \upsilon _i ,\upsilon _j \} $ in G. This problem is shown to have upper and lower bounds of $\Theta (n\log n)$ linear comparisons if G is any dense graph. The proof of the lower bound involves showing that any dense graph must contain a subgraph with many Hamiltonian paths, and demonstrating the relevance of these Hamiltonian paths to a geometric argument. In addition, we exhibit relatively sparse graphs for which the same lower bound holds, and relatively dense graphs for which a linear upper bound holds.