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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .