<p>If every sequence has length 3, the problem is known as <strong>Betweenness</strong>. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version of this problem is NP-hard. Chor and Sudan [2] proved that it is SNP-hard. </p>

<p>The best known approximation algorithm for the problem, by Chor and Sudan, satisfies 1/2 of all constraints if the instance is completely satisfiable.</p>

<p>[1] J. Opantry. <em>Total Ordering Problem, SIAM Journal on Computing</em>, 8(1):111—114, Feb. 1979.</p>

<p>[2] B. Chor and M. Sudan. <em>A geometric approach to betweenness</em>, SIAM Journal on Discrete
Mathematics, 11(4):511-523, Nov. 1998.</p>

<p><strong>Edits:</strong> clarified that the decision version of the problem is NP-hard.</p>

CC BY-SA 3.0
2012-06-29T19:58:37.850Z
Yury, does that mean that the decision problem of whether all constraints can be satisfied is also hard?
Chandra Chekuri
CC BY-SA 3.0
2012-06-29T20:00:21.797Z
Yes, the decision problem is NP-hard. Moreover, for some $\epsilon > 0$ it is NP-hard to satisfy even a $1-\epsilon$ fraction of all constraints (i.e. the corresponding promise problem is NP-hard).
Yury
CC BY-SA 3.0
2012-06-29T20:04:09.920Z
If the instance is **not** _completely satisfiable_, the problem is very hard: of course, you can satisfy $1/3$ of all constraints by taking a random order; but it is UGC-hard to satisfy $1/3+ \varepsilon$ of all constraints if $OPT = 1 -\varepsilon$ for every constant $\varepsilon > 0$ [Charikar, Guruswami, Manokaran — CCC 2009].
Yury
CC BY-SA 3.0
2012-06-30T16:24:26.140Z
my question might be stupid.  but does the 3-regular ($|\sigma_i| =3$ for all $i$) hardness extends to 4-regular naturally?
Yixin Cao
CC BY-SA 3.0
2012-06-30T18:54:56.593Z
Yes, here is a reduction. Consider a 3-regular instance ${\cal I}$. Introduce a new variable $y_i$ for every sequence $\sigma_i$. Let $\sigma_i'$ be a sequence obtained by appending $y_i$ to the end of $\sigma_i$. We get a 4-regular instance ${\cal I}'$ on vertices $V \cup\{y_i\}$ with sequences $\{\sigma_i'\}$. It is easy to see that ${\cal I}'$ is satisfiable if ${\cal I}$ was satisfiable — take the solution for ${\cal I}$, put each $y_i$ either before all vertices in $V$ or after all vertices in $V$ depending on the orientation of $\sigma_i$ (the relative order of $\{y_i\}$ is irrelevant).
Yury
CC BY-SA 3.0
2012-06-30T18:58:09.647Z
On the other hand, if ${\cal I}'$ is satisfiable then ${\cal I}$ is also satisfiable since we can just restrict the ordering to $V$.
Yury
CC BY-SA 3.0
2012-06-29T19:51:25.943Z
2012-06-29T20:23:51.937Z
2012-06-29T20:23:51.937Z
Yury
<p>If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with each of the partial orders). </p>

<p>I've come across a variation:</p>

<blockquote>
  <p>Fix a set $V$. You're given sequences $\sigma_1, \ldots \sigma_k$ of
  elements drawn from $V$ without repetition (the sequences are of
  length between 1 and $|V|$). </p>
  
  <p>Is there a way to fix orientations for each of the sequences (either
  forward or reverse) so that the resulting collection of chains (viewed
  as a partial order) admits an extension ?</p>
</blockquote>

<p>Is this problem well-known ? </p>

<p><strong>Note:</strong> The orientation is chosen for an entire sequence. So if the sequence is $1-2-4-5$, you can either keep it that way, or flip it to $5-4-2-1$, but you can't do anything else. </p>

CC BY-SA 3.0
2012-06-29T19:32:33.560Z
If each of the sequences are of length $2$ then one can think of each sequence as an undirected edge and we are asking whether an undirected graph can be oriented to be a DAG - iff if there is no cycle. But a greedy algorithm also works. Start with an edge and orient it arbitrarily and keep going as long as you can and if you get stuck you know it is not possible. Did you try that for your variation? Seems like it may work.
Chandra Chekuri
CC BY-SA 3.0
2012-06-29T19:52:28.000Z
Er, every undirected graph can be oriented to be a DAG. Just choose an ordering of the vertices and use that ordering to orient the edges.
David Eppstein
CC BY-SA 3.0
2012-06-29T19:56:28.990Z
You are right of course, me not thinking straight.
Chandra Chekuri
CC BY-SA 3.0
2012-06-29T20:41:33.437Z
In my variation each subsequence has length exactly 4, so Yury's answer kicks in. My only hope at this point is that the subsequences have very special structure and are related to each other, so maybe something specific to the problem would help. But there's no general hammer.
Suresh Venkat
<ds.algorithms><reference-request><order-theory>
A question on linear extensions of partial orders
Suresh Venkat
# A question on linear extensions of partial orders

(Asked by: username_0 on 2012-06-29)

If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with each of the partial orders).

I've come across a variation:

> Fix a set $V$. You're given sequences $\sigma\_1, \ldots \sigma\_k$ of
> elements drawn from $V$ without repetition (the sequences are of
> length between 1 and $|V|$).
>
> Is there a way to fix orientations for each of the sequences (either
> forward or reverse) so that the resulting collection of chains (viewed
> as a partial order) admits an extension ?

Is this problem well-known ?

**Note:** The orientation is chosen for an entire sequence. So if the sequence is $1-2-4-5$, you can either keep it that way, or flip it to $5-4-2-1$, but you can't do anything else.

**Tags:** ds.algorithms, reference-request, order-theory

> **Comments:**
> **username_1**: If each of the sequences are of length $2$ then one can think of each sequence as an undirected edge and we are asking whether an undirected graph can be oriented to be a DAG - iff if there is no cycle. But a greedy algorithm also works. Start with an edge and orient it arbitrarily and keep going as long as you can and if you get stuck you know it is not possible. Did you try that for your variation? Seems like it may work.  
> **username_2**: Er, every undirected graph can be oriented to be a DAG. Just choose an ordering of the vertices and use that ordering to orient the edges.  
> **username_1**: You are right of course, me not thinking straight.  
> **username_0**: In my variation each subsequence has length exactly 4, so username_3's answer kicks in. My only hope at this point is that the subsequences have very special structure and are related to each other, so maybe something specific to the problem would help. But there's no general hammer.  

---

## 1 answers

### Answer by username_3 on 2012-06-29. Score: 14 | Accepted answer

If every sequence has length 3, the problem is known as **Betweenness**. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version of this problem is NP-hard. Chor and Sudan [2] proved that it is SNP-hard.

The best known approximation algorithm for the problem, by Chor and Sudan, satisfies 1/2 of all constraints if the instance is completely satisfiable.

[1] J. Opantry. *Total Ordering Problem, SIAM Journal on Computing*, 8(1):111—114, Feb. 1979.

[2] B. Chor and M. Sudan. *A geometric approach to betweenness*, SIAM Journal on Discrete
Mathematics, 11(4):511-523, Nov. 1998.

**Edits:** clarified that the decision version of the problem is NP-hard.

> **Comments:**
> **username_1**: username_3, does that mean that the decision problem of whether all constraints can be satisfied is also hard?  
> **username_3**: Yes, the decision problem is NP-hard. Moreover, for some $\epsilon > 0$ it is NP-hard to satisfy even a $1-\epsilon$ fraction of all constraints (i.e. the corresponding promise problem is NP-hard).  
> **username_3**: If the instance is **not** _completely satisfiable_, the problem is very hard: of course, you can satisfy $1/3$ of all constraints by taking a random order; but it is UGC-hard to satisfy $1/3+ \varepsilon$ of all constraints if $OPT = 1 -\varepsilon$ for every constant $\varepsilon > 0$ [Charikar, Guruswami, Manokaran — CCC 2009].  
> **username_4**: my question might be stupid.  but does the 3-regular ($|\sigma_i| =3$ for all $i$) hardness extends to 4-regular naturally?  
> **username_3**: Yes, here is a reduction. Consider a 3-regular instance ${\cal I}$. Introduce a new variable $y_i$ for every sequence $\sigma_i$. Let $\sigma_i'$ be a sequence obtained by appending $y_i$ to the end of $\sigma_i$. We get a 4-regular instance ${\cal I}'$ on vertices $V \cup\{y_i\}$ with sequences $\{\sigma_i'\}$. It is easy to see that ${\cal I}'$ is satisfiable if ${\cal I}$ was satisfiable — take the solution for ${\cal I}$, put each $y_i$ either before all vertices in $V$ or after all vertices in $V$ depending on the orientation of $\sigma_i$ (the relative order of $\{y_i\}$ is irrelevant).  
> **username_3**: On the other hand, if ${\cal I}'$ is satisfiable then ${\cal I}$ is also satisfiable since we can just restrict the ordering to $V$.  

---

