For such a data set, the problem of the existence of a Hamiltonian path is equivalent to the existence of a path graphical model with score equal to k = γ + (| V | − 1) × β where |V| = n is the number of vertices in the undirected graph G. Thus, to reduce the HP problem to the OP problem one needs to efficiently construct a polynomial sized data set with these properties. In other words, by such a construction, a general HP decision problem can be transformed into an OP decision problem. Because the size of the input to the OP problem is a polynomial function of the size of the input for the HP problem, if one can find an algorithm solve the OP problem in polynomial time then all NP-complete problems can be solved in polynomial time.

I construct a data set for graph G assuming that each variable is ternary to satisfy condition (i). For each pair of vertices X i and X j ( i < j ) for which there is an edge in G i add the following 8 cases in which every variable X k ( k ≠ i,j) is zero.

| X 1 . . . X i   |
|-----------------|
| 0...0           |
| 0 . . . 0       |
| 0 . . . 0       |
| 0...0           |
| 0...0           |
| 0 . . . 0       |
| 0 . . . 0       |
| 0 . . . 0       |

| 1   |
|-----|
| 1   |
| 2   |
| 2   |
| 2   |
| 2   |

| Xi+1   |
|--------|
| 0...0  |
| 0...0  |
| 0...0  |
| 0...0  |
| 0...0  |
| 0...0  |
| 0...0  |
| 0...0  |

1 1

| 0...0     |
|-----------|
| 0...0     |
| 0 . . . 0 |
| 0 . . . 0 |
| 0...0     |
| 0 . . . 0 |
| 0 . . . 0 |
| 0...0     |

| 1   |
|-----|
| 1   |
| 2   |
| 2   |
| 2   |
| 2   |

2 1 2 2

| x     | j+l . . . . . .   |
|-------|-------------------|
| 0...0 |                   |
| 0...0 |                   |
| 0...0 |                   |
| 0...0 |                   |
| 0...0 |                   |
| 0...0 |                   |
| 0...0 |                   |
| 0...0 |                   |

For each pair of vertices X i and X i ( i < j ) for which there is not an edge in G i add the following 8 cases.

2 2 1 1 2 2 For a set of cases constructed as described above, the pairwise counts for a pair of variables

| 0...0     |
|-----------|
| 0...0     |
| 0 . . . 0 |
| 0...0     |
| 0...0     |
| 0...0     |
| 0...0     |
| 0...0     |

X i and X i connected by an edge in G are 0 X,

![0_image_0.png](0_image_0.png)

2

$\phi$. 
X j

| 0 . . . . 0   |
|---------------|
| 0...0         |
| 0...0         |
| 0...0         |
| 0...0         |
| 0...0         |
| 0...0         |
| 0...0         |

3 l 3
2