Fix an positive integer $N$.

A row means any linear ordering $R=(n_i)_{0\leq i <N}$ of the additive group ${\Bbb Z}/N{\Bbb Z}$.

Call $R$ a (generalized) all-interval row if the elements of the sequence $(n_i-n_{i-1})_{1\leq i <N}$ exhaust $({\Bbb Z}/N{\Bbb Z})\setminus \{0\}$. (This requires even $N$.)

I would like to know if the following decision problem is NP-complete:

Given $M<N$ and a sequence $S=(n_i)_{0\leq i <M}$ with $n_i\in {\Bbb Z}/N{\Bbb Z}$, does $S$ extend to an all interval row?

  • 1
    $\begingroup$ Do we know that it's in NP? (If $M \ll N$, it seems at least not immediately obvious, e.g. the input could have size polylog(N) while a full row witnessing the extension would have size $N\log N$.) $\endgroup$ – usul Apr 18 '14 at 2:53
  • 1
    $\begingroup$ @usul -- You make an interesting point, but I intended that N serve as the size measure of the problem instance regardless of the size of M. That said, calculations do suggest that very short sequences (not themselves displaying forbidden repetitions) always do extend. It would be interesting to me to know what one could prove along these lines (or even what one should conjecture!). $\endgroup$ – David Feldman Apr 18 '14 at 3:55
  • 1
    $\begingroup$ Maybe you can find some interesting results in the literature of graceful labelings of trees. en.wikipedia.org/wiki/Graceful_labeling $\endgroup$ – Vinicius dos Santos Apr 18 '14 at 4:54
  • 2
    $\begingroup$ So you supply $N$ in unary ? otherwise $N$ would not really serve as a size measure. $\endgroup$ – Suresh Venkat Apr 18 '14 at 5:42
  • 1
    $\begingroup$ Thank you @ViniciusdosSanto...but is there a literature about an analogue of graceful labels for digraphs? That would seem the relevant concept for my question since I have $n_{i+1}-n_i$, not $|n_{i+1}-n_i|$. Is there a directed version of the Ringel conjecture? I'm thinking complete digraphs and rooted trees, but with some amendment to avoid parity issues. Otherwise even a complete digraph on 3 nodes (so 6 edges) is trouble for a path of length 2 rooted at a leaf. $\endgroup$ – David Feldman Apr 18 '14 at 18:47

Your Answer

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

Browse other questions tagged or ask your own question.