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 now also asked the same question on Theoretical Computer Science since after two weeks of no response here I thought that this might be the better place for this question.

Improve this question
$\endgroup$
3
  • $\begingroup$ This is a well-written question, I think. Minor remars: (0) currently the OP doesn't contain a single ?-mark. (1) If "$s=s_1s_1\dotsc s_k$ be a word with letters in S such that each element in $S$ occur exactly once in $s$." is taken literally ${}_{\text{(grammatical aside: the use of the subjunctive mood 'occur' seems wrong/hyper-correct here)}}$, then the usual way to say this would simply be ' and $s=s_1s_2\dotsc s_k$ is a permutation of $S$ ' . I find it not easy to figure out whether this is the intended interpretation. Would you please make this clearer? $\endgroup$
    – Peter Heinig
    Commented Oct 6, 2017 at 11:35
  • 1
    $\begingroup$ @PeterHeinig Thanks for your remarks! (0) I will add a question to make clear what I'm actually asking. (1) That's indeed the correct interpretation, I will change this. $\endgroup$
    – Axel Dahlberg
    Commented Oct 6, 2017 at 11:43
  • 1
    $\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
    Commented Oct 22, 2017 at 12:34

1 Answer 1

Reset to default
1
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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