<p>Fix an positive integer $N$.  </p>

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

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

<p>I would like to know if the following decision problem is NP-complete:</p>

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

CC BY-SA 3.0
2014-04-18T02:53:38.053Z
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$.)
usul
CC BY-SA 3.0
2014-04-18T03:55:27.130Z
@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!).
David Feldman
CC BY-SA 3.0
2014-04-18T04:08:04.487Z
The tabulations here may be of interest:

https://oeis.org/search?q=1%2C2%2C12%2C144%2C1928&language=english&go=Search

Heuristically, there are $(N-1)!$ rows that begin with 0, and
$(N-1)!$ legal first differences out $(N-1)^{N-1}$ sequences possible a priori as first differences.  For $N=18$, the largest search I've carried out, the heuristic overestimates by a mere 47.5%.  That suggests to me that an appeal to probabilistic heuristics for making a conjecture about extending short sequences might prove fruitful.
David Feldman
CC BY-SA 3.0
2014-04-18T04:54:44.807Z
Maybe you can find some interesting results in the literature of graceful labelings of trees.
http://en.wikipedia.org/wiki/Graceful_labeling
Vinicius dos Santos
CC BY-SA 3.0
2014-04-18T05:42:38.467Z
So you supply $N$ in unary ? otherwise $N$ would not really serve as a size measure.
Suresh Venkat
CC BY-SA 3.0
2014-04-18T17:31:26.223Z
Start with $M = 0$. Does there always exist an all-interval row for any given $N$?
argentpepper
CC BY-SA 3.0
2014-04-18T18:18:40.940Z
@argentpepper
Well, for any given _even_ $N$, yes.
This example, mod 12:  0 11  1 10  2  9  3  8  4  7  5  6
generalizes in an obvious way.
For odd $N$, no, for trivial reasons.
David Feldman
CC BY-SA 3.0
2014-04-18T18:39:07.003Z
@SureshVenkat
 
>So you supply N in unary? 

Sure, exactly.
Though I reiterate...I conjecture that it doesn't make a difference, that "short" (some sufficiently root of $N$ say) sequences with no repetitions of "notes" or "intervals" always extend.  But I confess I should actually work the probability calculation before I say I feel fully confident about this.
David Feldman
CC BY-SA 3.0
2014-04-18T18:47:46.750Z
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.
David Feldman
CC BY-SA 3.0
2014-04-19T02:01:25.463Z
Call a sequence critical if
1) it begins with 0;
2) it does not extend to an all-interval row;
3) every proper initial segment does extend to an all-interval row; 
4) the sequence repeats no "notes" or "intervals" and does not contain N/2 (which must come last in an all-interval row).

For N=14 the numbers of critical sequences of length 2,3,4,5 etc. (correct me if I'm wrong) equal 0,0,0,114,6276,70740,121476,101844,66474,27744, 8130.  In particular, all not obviously flawed sequences of length 4 extend all the way to 14.
David Feldman
CC BY-SA 3.0
2014-04-19T19:25:11.723Z
@ViniciusdosSantos Curiously, though I count 3856 all-interval rows starting with 0 and having length twelve,  0 11  1 10  2  9  3  8  4  7  5  6 seems to be the _unique_ such graceful labeling of a path.
David Feldman
<np-complete>
Complexity question from mathematical music theory
David Feldman
# Complexity question from mathematical music theory

(Asked by: username_0 on 2014-04-18)

Fix an positive integer $N$.

A *row* means any linear ordering $R=(n\_i)\_{0\leq i 

Call $R$ a (generalized) *all-interval row* if the elements of the sequence $(n\_i-n\_{i-1})\_{1\leq i 

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

Given $M

**Tags:** np-complete
> **Comments:**
> **username_1**: 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$.)  
> **username_0**: @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!).  
> **username_0**: The tabulations here may be of interest:  https://oeis.org/search?q=1%2C2%2C12%2C144%2C1928&language=english&go=Search  Heuristically, there are $(N-1)!$ rows that begin with 0, and $(N-1)!$ legal first differences out $(N-1)^{N-1}$ sequences possible a priori as first differences.  For $N=18$, the largest search I've carried out, the heuristic overestimates by a mere 47.5%.  That suggests to me that an appeal to probabilistic heuristics for making a conjecture about extending short sequences might prove fruitful.  
> **username_2**: Maybe you can find some interesting results in the literature of graceful labelings of trees. http://en.wikipedia.org/wiki/Graceful_labeling  
> **username_3**: So you supply $N$ in unary ? otherwise $N$ would not really serve as a size measure.  
> **username_4**: Start with $M = 0$. Does there always exist an all-interval row for any given $N$?  
> **username_0**: @argentpepper Well, for any given _even_ $N$, yes. This example, mod 12:  0 11  1 10  2  9  3  8  4  7  5  6 generalizes in an obvious way. For odd $N$, no, for trivial reasons.  
> **username_0**: @SureshVenkat   >So you supply N in unary?   Sure, exactly. Though I reiterate...I conjecture that it doesn't make a difference, that "short" (some sufficiently root of $N$ say) sequences with no repetitions of "notes" or "intervals" always extend.  But I confess I should actually work the probability calculation before I say I feel fully confident about this.  
> **username_0**: 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.  
> **username_0**: Call a sequence critical if 1) it begins with 0; 2) it does not extend to an all-interval row; 3) every proper initial segment does extend to an all-interval row;  4) the sequence repeats no "notes" or "intervals" and does not contain N/2 (which must come last in an all-interval row).  For N=14 the numbers of critical sequences of length 2,3,4,5 etc. (correct me if I'm wrong) equal 0,0,0,114,6276,70740,121476,101844,66474,27744, 8130.  In particular, all not obviously flawed sequences of length 4 extend all the way to 14.  
> **username_0**: @ViniciusdosSantos Curiously, though I count 3856 all-interval rows starting with 0 and having length twelve,  0 11  1 10  2  9  3  8  4  7  5  6 seems to be the _unique_ such graceful labeling of a path.  

---

## 0 answers

