<p>The SOET problem is NP-Complete as we show in the following paper:</p>

<p>Axel Dahlberg, Jonas Helsen, Stephanie Wehner, <strong>How to transform graph states using single-qubit operations: computational complexity and algorithms</strong>, 
 <a href="https://arxiv.org/abs/1805.05306" rel="nofollow noreferrer">CoRR abs/1805.05306 (2018)</a>.</p>

<p>See Corollary 3.4.1</p>

CC BY-SA 4.0
2018-07-25T04:43:45.430Z
2018-07-25T06:48:24.883Z
2018-07-25T06:48:24.883Z
Axel Dahlberg
<p>I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this problem or proving that this is actually in NP-hard would settle this question for me. Below I describe the problem, give two examples of instances to the problem and explain what I have realized so far. To be precise, my questions are:</p>

<ul>
<li><p>What is the time-complexity of this problem? </p></li>
<li><p>Is this problem NP-hard?</p></li>
<li><p>If it exists, what is an algorithm that solves this problem in polynomial time in terms of both $n$ and $k$? (see below)</p></li>
</ul>

<p><strong>The SOET problem</strong></p>

<p>Given a 4-regular graph $G=(V,E)$, i.e. a graph where each vertex have degree 4, the problem is to find a semi-ordered Eulerian tour (defined below). Note that the graph is not assumed to be simple, so multi-edges and self-loops are allowed.</p>

<p><em>Definition (semi-ordered Eulerian tour):</em>
Let $S\subseteq V$ be a subset of the vertices in $G$ and $s=s_1s_2\dots s_k$ be a permutation of $S$. The Eulerian tour $U$ is a semi-ordered Eulerian tour with respect to $S$ if, $U=As_1Bs_2\dots s_kXs_1Ys_2\dots s_kZ$ for some $s$ and where $A,B\dots,X,Y,\dots,Z$ are words with letters in $V\setminus S$. That is, $U$ traverses $s$ in some order once and then again in the same order. To be clear, which specific $s$ that satisfies this is unimportant.</p>

<p>Note that since $G$ is 4-regular an Eulerian tour always exists and furthermore it will pass each vertex exactly twice.</p>

<p><strong>Examples</strong></p>

<p>Here I give two examples of 4-regular graphs. The first one, <a href="https://i.sstatic.net/te1yc.jpg" rel="noreferrer">G_1</a>, there is a SOET with respect to $\{a,b,c,d\}$, since there is a Eulerian tour $U=abcdaebced$. In the second example, <a href="https://i.sstatic.net/y1SYR.jpg" rel="noreferrer">G_2</a>, there is none.</p>

<p><strong>Current status</strong></p>

<p>I have realized that this problem is at least fixed-parameter tractable in terms of $k$, i.e. there is an algorithm with time-complexity $\mathcal{O}(f(k)p(n))$, where $k=|S|$, $n=|V|$ and $p$ is some polynomial. This can be seen by mapping the problem to $k!k^3$ edge-disjoint paths problems (DPP) where you try to find paths between pairs of vertices in $S$. This has to be done for all permutations of the vertices in $S$, the reason for the factor $k!$ in the number of DPP:s. Furthermore each vertex has to be split into two vertices and connected by edges in one out of three ways (vertically, horizontally or diagonally), to actually give a Eulerian tour. This are in total another $3^k$ DPP:s. Note that this does not necessarily exclude the possibility of an algorithm which is also polynomial in $k$.</p>

<p><em>Note regarding duplicate:</em></p>

<p><em>I have also asked <a href="https://mathoverflow.net/questions/282743/complexity-of-finding-semi-ordered-eulerian-tours-in-a-4-regular-graph">the same question</a> on MathOverflow but after two weeks of no response I thought that this might be the better place for this question.</em></p>

CC BY-SA 3.0
2017-10-17T19:42:17.213Z
Sorry to inform you that Peter Heinig was wrong about "$s=s_1s_2\dots s_k$ be a word with letters in $S$ such that each element in $S$ occur exactly once in $s$" being equivalent to "$s=s_1s_2\dots s_k$ is a **permutation** of $S$". It is used as a *total order* on $S$ here, and not as a *permutation* of $S$.
Thomas Klimpel
CC BY-SA 3.0
2017-10-17T20:05:13.363Z
Okay, that was what I was worried about and why I first wrote "$s=s_1s_2\dots s_k$ be a word with letters in $S$ such that each element in $S$ occur exactly once in $s$", but when I had a response that this was confusing and that it was equivalent to a permutation of $S$ I changed it. To be honest, I am not really sure why this is not a permutation of $S$. Is there at least a one-to-one correspondence?
Thanks for your comment!
Axel Dahlberg
CC BY-SA 3.0
2017-10-22T12:35:09.140Z
I have recently managed to prove that this problem is indeed NP-Complete. This will be included in a paper I am currently writing, so when I have written the proof down I will either also provide it here or give a link to the paper. But it is a bit too complicated to quickly give a satisfactory answer at this point.
Axel Dahlberg
<graph-theory><graph-algorithms><time-complexity>
Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
Axel Dahlberg
# Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

(Asked by: username_0 on 2017-10-16)

I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this problem or proving that this is actually in NP-hard would settle this question for me. Below I describe the problem, give two examples of instances to the problem and explain what I have realized so far. To be precise, my questions are:

* What is the time-complexity of this problem?
* Is this problem NP-hard?
* If it exists, what is an algorithm that solves this problem in polynomial time in terms of both $n$ and $k$? (see below)

**The SOET problem**

Given a 4-regular graph $G=(V,E)$, i.e. a graph where each vertex have degree 4, the problem is to find a semi-ordered Eulerian tour (defined below). Note that the graph is not assumed to be simple, so multi-edges and self-loops are allowed.

*Definition (semi-ordered Eulerian tour):*
Let $S\subseteq V$ be a subset of the vertices in $G$ and $s=s\_1s\_2\dots s\_k$ be a permutation of $S$. The Eulerian tour $U$ is a semi-ordered Eulerian tour with respect to $S$ if, $U=As\_1Bs\_2\dots s\_kXs\_1Ys\_2\dots s\_kZ$ for some $s$ and where $A,B\dots,X,Y,\dots,Z$ are words with letters in $V\setminus S$. That is, $U$ traverses $s$ in some order once and then again in the same order. To be clear, which specific $s$ that satisfies this is unimportant.

Note that since $G$ is 4-regular an Eulerian tour always exists and furthermore it will pass each vertex exactly twice.

**Examples**

Here I give two examples of 4-regular graphs. The first one, [G\_1](https://i.sstatic.net/te1yc.jpg), there is a SOET with respect to $\{a,b,c,d\}$, since there is a Eulerian tour $U=abcdaebced$. In the second example, [G\_2](https://i.sstatic.net/y1SYR.jpg), there is none.

**Current status**

I have realized that this problem is at least fixed-parameter tractable in terms of $k$, i.e. there is an algorithm with time-complexity $\mathcal{O}(f(k)p(n))$, where $k=|S|$, $n=|V|$ and $p$ is some polynomial. This can be seen by mapping the problem to $k!k^3$ edge-disjoint paths problems (DPP) where you try to find paths between pairs of vertices in $S$. This has to be done for all permutations of the vertices in $S$, the reason for the factor $k!$ in the number of DPP:s. Furthermore each vertex has to be split into two vertices and connected by edges in one out of three ways (vertically, horizontally or diagonally), to actually give a Eulerian tour. This are in total another $3^k$ DPP:s. Note that this does not necessarily exclude the possibility of an algorithm which is also polynomial in $k$.

*Note regarding duplicate:*

*I have also asked [the same question](https://mathoverflow.net/questions/282743/complexity-of-finding-semi-ordered-eulerian-tours-in-a-4-regular-graph) on MathOverflow but after two weeks of no response I thought that this might be the better place for this question.*

**Tags:** graph-theory, graph-algorithms, time-complexity

> **Comments:**
> **username_1**: Sorry to inform you that Peter Heinig was wrong about "$s=s_1s_2\dots s_k$ be a word with letters in $S$ such that each element in $S$ occur exactly once in $s$" being equivalent to "$s=s_1s_2\dots s_k$ is a **permutation** of $S$". It is used as a *total order* on $S$ here, and not as a *permutation* of $S$.  
> **username_0**: Okay, that was what I was worried about and why I first wrote "$s=s_1s_2\dots s_k$ be a word with letters in $S$ such that each element in $S$ occur exactly once in $s$", but when I had a response that this was confusing and that it was equivalent to a permutation of $S$ I changed it. To be honest, I am not really sure why this is not a permutation of $S$. Is there at least a one-to-one correspondence? Thanks for your comment!  
> **username_0**: I have recently managed to prove that this problem is indeed NP-Complete. This will be included in a paper I am currently writing, so when I have written the proof down I will either also provide it here or give a link to the paper. But it is a bit too complicated to quickly give a satisfactory answer at this point.  

---

## 1 answers

### Answer by username_0 on 2018-07-25. Score: 3 | Accepted answer

The SOET problem is NP-Complete as we show in the following paper:

username_0, Jonas Helsen, Stephanie Wehner, **How to transform graph states using single-qubit operations: computational complexity and algorithms**,
[CoRR abs/1805.05306 (2018)](https://arxiv.org/abs/1805.05306).

See Corollary 3.4.1


---

