13
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Jun 29, 2012 at 19:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jun 29, 2012 at 19:52
  • $\begingroup$ You are right of course, me not thinking straight. $\endgroup$
    – Chandra Chekuri
    Commented Jun 29, 2012 at 19:56
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Jun 29, 2012 at 20:41

1 Answer 1

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yury, does that mean that the decision problem of whether all constraints can be satisfied is also hard? $\endgroup$
    – Chandra Chekuri
    Commented Jun 29, 2012 at 19:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – Yury
    Commented Jun 29, 2012 at 20:00
  • 4
    $\begingroup$ 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]. $\endgroup$
    – Yury
    Commented Jun 29, 2012 at 20:04
  • $\begingroup$ my question might be stupid. but does the 3-regular ($|\sigma_i| =3$ for all $i$) hardness extends to 4-regular naturally? $\endgroup$
    – Yixin Cao
    Commented Jun 30, 2012 at 16:24
  • 1
    $\begingroup$ 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). $\endgroup$
    – Yury
    Commented Jun 30, 2012 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.