Name
Abstract | ||
|---|---|---|
We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the $n!$ Hamilton cycles in a complete directed graph on $n+1$ vertices corresponds with each of the $n!$ $n$-permutation matrices $P$, such that $p_{u,i}=1$ if and only if the $i^{th}$ arc in a cycle enters vertex $u$, starting and ending at vertex $n+1$. A graph instance ($G$) is initially coded as exclusion set $E$, whose members are pairs of components of $P$, ${p_{u,i} ,p_{v,i+1}}, i=1,n-1$, for each arc $(u,v)$ not in $G$. For each ${p_{u,i} ,p_{v,i+1}}in E$, the set of $P$ satisfying $p_{u,i}=p_{v,i+1}=1$ correspond with a set of cycles not in $G$. Accounting for all arcs not in $G$, $E$ codes precisely the set of cycles not in $G$. A doubly stochastic-like $mathcal{O}$($n^4$) formulation of the Hamilton cycle decision problem is then constructed. Each ${p_{u,i} ,p_{v,j}}$ is coded as variable $q_{u,i,v,j}$ such that the set of integer extrema is the set of all permutations. We model $G$ by setting each $q_{u,i,v,j}=0$ in correspondence with each ${p_{u,i} ,p_{v,j}}in E$ such that for non-Hamiltonian $G$, integer solutions cannot exist. We recognize non-Hamiltonicity by iteratively deducing additional $q_{u,i,v,j}$ that can be set zero and expanding $E$ until the formulation becomes infeasible, in which case we recognize that no integer solutions exists i.e. $G$ is decided non-Hamiltonian. Over 100 non-Hamiltonian graphs (10 through 104 vertices) and 2000 randomized 31 vertex non-Hamiltonian graphs are tested and correctly decided non-Hamiltonian. For Hamiltonian $G$, the complement of $E$ provides information about covers of matchings, perhaps useful in searching for cycles. We also present an example where the algorithm fails to deduce any integral value for any $q_{u,i,v,j}$ i.e. $G$ is undecided. |
Year | Venue | Field |
|---|---|---|
2016 | international symposium on algorithms and computation | Graph,Discrete mathematics,Combinatorics,Decision problem,Computer science,Hamiltonian path,Algorithm |
DocType | Volume | Citations |
Journal | abs/1611.01710 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| E. R. Swart | 1 | 0 | 0.68 |
| S. J. Gismondi | 2 | 0 | 0.34 |
| N. R. Swart | 3 | 0 | 0.34 |
| C. E. Bell | 4 | 0 | 0.34 |
| A. Lee | 5 | 11 | 2.05 |