3
$\begingroup$

Let $\Sigma$ be a small, finite alphabet. Suppose we are given ${n\choose 2}$ sets $S_{i,j}$, where $S_{i,j} \subseteq \Sigma \times\Sigma$. I'd like to determine whether there exists a sequence $x_1,x_2,\dots,x_n \in \Sigma$ such that $(x_i,x_j) \in S_{i,j}$ for all $i,j$, and if so, find an example of such a sequence.

Are there any good algorithms for this problem?

Also: Suppose I model each set $S_{i,j}$ as a randomly chosen subset of $\Sigma \times \Sigma$ where each of the possible elements is included in $S_{i,j}$ with probability $p$ (independently of everything else). Thus, the expected size of each $S_{i,j}$ is $p \cdot |\Sigma|^2$. Is there any characterization of the range of values of $p$ for which this problem should be efficiently solvable?

(In my application, $|\Sigma|=10$, if that helps.)

This looks like some sort of 2-CSP (constraint satisfaction problem, where each constraint is on exactly 2 variables), but I don't know what more we might be able to say.

$\endgroup$
  • $\begingroup$ What do you know about its hardness? Do you already have a reduction? $\endgroup$ – Parham Nov 3 '13 at 12:49
  • $\begingroup$ @MahmoudAlimohamadi, thanks for asking! I know nothing, so anything would be interesting. (I suspect it'll probably be NP-complete in the general case, since I think I remember reading that 2-CSP is NP-complete. So I'm especially interested in any "phase transition" behavior, i.e., if there's anything we can say about hardness as a function of $p$, in the random model specified above.) This came up in an application in the area of cryptography/computer security. $\endgroup$ – D.W. Nov 3 '13 at 20:59
  • $\begingroup$ Maybe I'm wrong but this seems much simpler. Can you not construct a graph where e = (x_1, x_2) in E iff e in S_{I, j}? Then going from the partial ordering to the total ordering should just be a run of topological sort. Correct me if I'm wrong. (I'm only taking the first portion of your question into account) $\endgroup$ – Francesco Gramano Apr 9 '14 at 10:38
  • $\begingroup$ @FrancescoGramano, can you elaborate a little further? Sounds interesting, but I'm not following yet. Certainly for each set $S_{i,j}$ I can get a graph with vertex set $\Sigma$ and edge set $S_{i,j}$, as you described. Is that what you meant? If so, this gives me ${n \choose 2}$ little graphs. Now what? $\endgroup$ – D.W. Apr 9 '14 at 14:40
  • $\begingroup$ In general you can go from having partial orderings of every pair of terms to a total ordering of a sequence of the terms if the graph G=(V,E) has no directed cycle (i.e., if e_1 = (v_i, v_j) in E and e_2 = (v_j, v_i) not in E for all i,j). My suggestion is to construct a graph G=(X,E) in which e = (x_i, x_j) in E iff (x_i, x_j) in S_{i,j}, then there exists a sequence x_1, ... , x_n in Sigma iff you can successfully run a topological sort (i.e., there are no directed edges) in the aforementioned graph. $\endgroup$ – Francesco Gramano Apr 9 '14 at 16:37

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.