You could expand the state space by including the subset of people visited so far. Also introduce two absorbing states, win and lose, and then use the usual approach to find the absorption probabilities.

For the example with 12 people, the only subsets you need to track are the four subsets of {5,7}, rather than all subsets of $\{1,\dots,12\}\setminus \{6\}$.

Let $w(i,S)$ denote the win probability starting with person $i$ and $S \subseteq \{5,7\}$ visited so far. Then $w(6,\{5,7\})=1$, $w(6,S)=0$ for $S\not=\{5,7\}$, and $$w(i,S) = \sum\limits_{j,T} p_{i,S,j,T}\ w(j,T),$$
where the transition probabilities $p_{i,S,j,T}$ are as follows (with 0, 5, 7, and 57 as shorthand for the corresponding subsets):

```
i S j T p(i,S,j,T)
1 0 2 0 0.5
1 0 12 0 0.5
1 5 2 5 0.5
1 5 12 5 0.5
1 7 2 7 0.5
1 7 12 7 0.5
1 57 2 57 0.5
1 57 12 57 0.5
2 0 1 0 0.5
2 0 3 0 0.5
2 5 1 5 0.5
2 5 3 5 0.5
2 7 1 7 0.5
2 7 3 7 0.5
2 57 1 57 0.5
2 57 3 57 0.5
3 0 2 0 0.5
3 0 4 0 0.5
3 5 2 5 0.5
3 5 4 5 0.5
3 7 2 7 0.5
3 7 4 7 0.5
3 57 2 57 0.5
3 57 4 57 0.5
4 0 3 0 0.5
4 0 5 5 0.5
4 5 3 5 0.5
4 5 5 5 0.5
4 7 3 7 0.5
4 7 5 57 0.5
4 57 3 57 0.5
4 57 5 57 0.5
5 5 4 5 0.5
5 5 6 5 0.5
5 57 4 57 0.5
5 57 6 57 0.5
6 5 6 5 1.0
6 7 6 7 1.0
6 57 6 57 1.0
7 7 6 7 0.5
7 7 8 7 0.5
7 57 6 57 0.5
7 57 8 57 0.5
8 0 7 7 0.5
8 0 9 0 0.5
8 5 7 57 0.5
8 5 9 5 0.5
8 7 7 7 0.5
8 7 9 7 0.5
8 57 7 57 0.5
8 57 9 57 0.5
9 0 8 0 0.5
9 0 10 0 0.5
9 5 8 5 0.5
9 5 10 5 0.5
9 7 8 7 0.5
9 7 10 7 0.5
9 57 8 57 0.5
9 57 10 57 0.5
10 0 9 0 0.5
10 0 11 0 0.5
10 5 9 5 0.5
10 5 11 5 0.5
10 7 9 7 0.5
10 7 11 7 0.5
10 57 9 57 0.5
10 57 11 57 0.5
11 0 10 0 0.5
11 0 12 0 0.5
11 5 10 5 0.5
11 5 12 5 0.5
11 7 10 7 0.5
11 7 12 7 0.5
11 57 10 57 0.5
11 57 12 57 0.5
12 0 1 0 0.5
12 0 11 0 0.5
12 5 1 5 0.5
12 5 11 5 0.5
12 7 1 7 0.5
12 7 11 7 0.5
12 57 1 57 0.5
12 57 11 57 0.5
```

Here are the resulting win probabilities $w(i,S)$ for the various states:
\begin{align}
i\backslash S &&\{\} &&\{5\} &&\{7\} &&\{5,7\} \\
1 &&1/11 &&5/11 &&7/11 &&1 \\
2 &&1/11 &&4/11 &&8/11 &&1 \\
3 &&1/11 &&3/11 &&9/11 &&1 \\
4 &&1/11 &&2/11 &&10/11 &&1 \\
5 && &&1/11 &&&&1 \\
6 && &&0 &&0 &&1 \\
7 && && &&1/11 &&1 \\
8 &&1/11 &&10/11 &&2/11 &&1 \\
9 &&1/11 &&9/11 &&3/11 &&1 \\
10 &&1/11 &&8/11 &&4/11 &&1 \\
11 &&1/11 &&7/11 &&5/11 &&1 \\
12 &&1/11 &&6/11 &&6/11 &&1
\end{align}
In particular, the desired win probability is $w(1,\{\}) = 1/11$.