7
$\begingroup$

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, 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, 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 on MathOverflow but after two weeks of no response I thought that this might be the better place for this question.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Thomas Klimpel Oct 17 '17 at 19:42
  • $\begingroup$ 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! $\endgroup$ – Axel Dahlberg Oct 17 '17 at 20:05
  • $\begingroup$ 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. $\endgroup$ – Axel Dahlberg Oct 22 '17 at 12:35
3
$\begingroup$

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

Axel Dahlberg, Jonas Helsen, Stephanie Wehner, How to transform graph states using single-qubit operations: computational complexity and algorithms, CoRR abs/1805.05306 (2018).

See Corollary 3.4.1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.