Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-22T07:11:10.606Z Has data issue: false hasContentIssue false
  • English
  • Français

On Random Betweenness Constraints

Published online by Cambridge University Press:  05 October 2010

ANDREAS GOERDT
ANDREAS GOERDT*
Affiliation:
Technische Universität Chemnitz, Fakultät für Informatik, Straße der Nationen 62, 09107 Chemnitz, Germany (e-mail: [email protected], http://www.tu-chemnitz.de/informatik/TI/)
Get access Rights & Permissions [Opens in a new window]

Abstract

Ordering constraints are formally analogous to instances of the satisfiability problem in conjunctive normal form, but instead of a boolean assignment we consider a linear ordering of the variables in question. A clause becomes true given a linear ordering if and only if the relative ordering of its variables obeys the constraint considered.

The naturally arising satisfiability problems are NP-complete for many types of constraints. We look at random ordering constraints. Previous work of the author shows that there is a sharp unsatisfiability threshold for certain types of constraints. The value of the threshold, however, is essentially undetermined. We pursue the problem of approximating the precise value of the threshold. We show that random instances of the betweenness constraint are satisfiable with high probability if the number of randomly picked clauses is ≤0.92n, where n is the number of variables considered. This improves the previous bound, which is <0.82n random clauses. The proof is based on a binary relaxation of the betweenness constraint and involves some ideas not used before in the area of random ordering constraints.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 5-6: Papers from the 2009 Oberwolfach Meeting on Combinatorics and Probability , November 2010 , pp. 775 - 790
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Achlioptas, D. and Moore, C. (2006) Random k-SAT: Two moments suffice to cross a sharp threshold. SIAM J. Comput. 36 740–762.Google Scholar
[2]Ailon, N. and Alon, N. (2007) Hardness of fully dense problems. Inform. Comput. 205 1117–1129.Google Scholar
[3]Beame, P., Karp, R., Pitassi, T. and Saks, M. (2002) The efficiency of resolution and Davis–Putnam procedures. SIAM J. Comput. 31 1048–1075.CrossRefGoogle Scholar
[4]Bodirsky, M. and Kára, J. (2008) The complexity of temporal constraint satisfaction problems. In Proc. 40th ACM Symposium on Theory of Computing (SToC), pp. 29–38.Google Scholar
[5]Bollobás, B. (1985) Random Graphs, Academic Press.Google Scholar
[6]Broder, A., Frieze, A. and Upfal, A. (1993) On the satisfiability and maximum satisfiability of random 3-CNF formulas. In Proc. 4th ACM–SIAM Symposium on Discrete Algorithms (SoDA), pp. 322–330.Google Scholar
[7]Chor, B. and Sudan, M. (1998) A geometric approach to betweenness. SIAM J. Discrete Math. 11 511–523.Google Scholar
[8]Christof, T., Jünger, M., Kececioglu, J., Mutzel, P. and Reinelt, G. (1997) A branch-and-cut approach to physical mapping with end-probes. In Proc. 1st Annual International Conference on Computational Molecular Biology (RECOMB), pp. 84–92.Google Scholar
[9]Dubois, O., Boufkhad, Y. and Mandler, J. (2000) Typical random 3-SAT formulae and the satisfiability threshold. In Proc. 11th ACM–SIAM Symposium on Discrete Algorithms (SoDA), pp. 126–127.Google Scholar
[10]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17–61.Google Scholar
[11]Friedgut, E. (2005) Hunting for sharp thresholds. Random Struct. Alg. 26 37–51.Google Scholar
[12]Goerdt, A. (2009) On random ordering constraints. In Proc. Computer Science in Russia (CSR), Vol. 5675 of Lecture Notes in Computer Science, Springer, pp. 105–116.Google Scholar
[13]Guttmann, W. and Maucher, M. (2006) Variations on an ordering theme with constraints. In Proc. 4th IFIP International Conference on Theoretical Computer Science (TCS), Vol. 209 of International Federation for Information Processing, Springer, pp. 77–90.Google Scholar
[14]Hatami, H. and Molloy, M. (2008) Sharp thresholds for constraint satisfaction problems and homomorphisms. Random Struct. Alg. 33 310–332.CrossRefGoogle Scholar
[15]Isli, A. and Cohn, A. G. (1998) An algebra for cyclic ordering of 2D orientation. In Proc. 15th American Conference on Artificial Intelligence (AAAI), AAAI/MIT Press, pp. 643–649.Google Scholar
[16]Karp, R. M. (1990) The transitive closure of a random digraph. Random Struct. Alg. 1 73–93.Google Scholar
[17]Molloy, M. (2002) Models and thresholds for random constraint satisfaction problems. In Proc. 34th ACM Symposium on Theory of Computing (SToC), pp. 209–217.CrossRefGoogle Scholar
[18]Molloy, M. (2005) Cores in random hypergraphs and Boolean formulas. Random Struct. Alg. 27 124–135.CrossRefGoogle Scholar
[19]Molloy, M. (2008) When does the giant component bring unsatisfiability? Combinatorica 28 693–734.Google Scholar
[20]Opatrny, J. (1979) Total ordering problem. SIAM J. Comput. 8 111–114.CrossRefGoogle Scholar
[21]Palasti, I. (1971) On the threshold distribution function of cycles in a directed random graph. Studia Scientiarum Math. Hungar. 6 67–73.Google Scholar