10
$\begingroup$

Suppose I want a necklace with $n$ beads labelled (bijectively) by $\{1, 2, \ldots n\}$, that is I want a cyclic order on $\{1, 2, \ldots, n\}$ (so for example $132$ is the same cyclic order as $321$ but different from $231$). Now suppose I know the cyclic order of some subsets of $\{1, 2, \ldots, n\}$ as they should appear in the necklace. I want to know what conditions on the subsets and their cyclic orders would make the necklace uniquely reconstructible, or given a set of subsets with orders how many compatible necklaces there are.

I feel like surely this is well studied (somewhere in the world of reconstructibility or elsewhere), but I'm not managing to find any results on it, so perhaps you can help me find where people have looked at this.

Thanks.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are the subsets allowed to intersect? Or interleave? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Sep 26, 2017 at 17:12
  • $\begingroup$ Does cyclic order come with direction? E.g., would cyclic orders 132 and 231 be considered the same? $\endgroup$
    – Max Alekseyev
    Commented Sep 27, 2017 at 0:08
  • $\begingroup$ Yes, 132 and 231 are different (hence "necklace", but these things are not as standard as they might be, so I will clarify in the question). $\endgroup$
    – Karen Yeats
    Commented Sep 27, 2017 at 18:32
  • $\begingroup$ In the application I have in mind the subsets would typically intersect and could potentially interleave. $\endgroup$
    – Karen Yeats
    Commented Sep 27, 2017 at 18:36

1 Answer 1

Reset to default
3
$\begingroup$

This problem is NP-complete, thus there is no easily verifiable condition that would be necessary and sufficient. In fact, it is enough if only some of the triples are prescribed, see Cyclic ordering is NP-complete by Galil and Megiddo. Another, closely related problem is Betweenness.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Are there any special cases of the problem that people have studied that are better behaved? Say if my subsets are guaranteed to have some special properties? In the application I have in mind they would be triples, but if there are further conditions that would make the problem easy that could be very interesting when translated back into conditions for niceness in the original application. $\endgroup$
    – Karen Yeats
    Commented Sep 29, 2017 at 13:36
  • $\begingroup$ Also, if I have as a hypothesis that there is a consistent order, but then want to know something about all the consistent orders (how many or construct them), does that end up being any easier? $\endgroup$
    – Karen Yeats
    Commented Sep 29, 2017 at 13:41
  • $\begingroup$ @Karen I don't know anything about your first question, but knowing that there exists a consistent order certainly won't help. If it did, then you could "pretend" to know that there is one, and use your algorithm to count/construct (a) consistent order(s). If your "pretence" was false, you would run into a contradiction, so eventually you could turn this into an algorithm to decide whether there's a consistent order or not. $\endgroup$
    – domotorp
    Commented Sep 29, 2017 at 19:14

You must log in to answer this question.

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