c 2012 by the paper authors. CLA 2012, pp. 317–325. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors.
Local Proceedings in ISBN 978–84–695–5252–0,
Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain.
This paper is motivated by understanding links between several parameters theory. that are onsidered in dierent areas su h as FCA, database, logi and graph
318 Laurent Beaudou, Mamadou Moustapha Kant´e and Lhouari Nourine Demetrovi s et al. [5℄ gave a hara terization of onvex sets of an impli ation basis. Proposition 1 is restri ted to betweenness relations.
The lattice of all betweenness relations: Structure and properties 319 under in lusion.
Theorem 1. is a losure system and therefore a latti e when stru tured FX shortest path betweenness (b) Convex sets of for G Proof. We prove this proposition point by point.
The lattice of all betweenness relations: Structure and properties 321 F1 ∧ F2 = FΣ1∪Σ2.
F1 ∨ F2 = FΣ1∩Σ2.
Thus, the o-atom asso iated to the impli ation is not [{a, b}, X \ {c}]. ab → c above but it is above , so that has at least two su F ′ F F that all meet-irredu ible elements are o-atoms of . FX tion 1, we know that from to , we remove at least an interval of the form F ′ F only su essor of and a betweenness su h that is . By Proposi- FΣ1 Σ2 F ′ FΣ2 322 Laurent Beaudou, Mamadou Moustapha Kant´e and Lhouari Nourine {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4}
The lattice of all betweenness relations: Structure and properties 323
324 Laurent Beaudou, Mamadou Moustapha Kant´e and Lhouari Nourine ases of betweenness relations (see for instan e [7℄ for the shortest path betweendatabase theory, and they have been proved NP- omplete [5,14,15℄ for general These problems have been studied in the several domains and spe ially in Therefore, we have the following. ness relation on graphs). It is known as the hull number of a betweenness relation. impli ation bases. The problem MK has been proved NP- omplete for parti ular of ould help to address this question. FX tational omplexity of the hydra number is open for betweenness relations, but The size of an optimal over is known as the hydra number [19℄. The ompuis NP- omplete for the general ase [11,15℄. We hope that the latti e stru ture
Question: Is there a set su h that and K ⊆ X |K| ≤ k KΣ = X? Input: a betweenness relation on and an integer. Σ X k Minimum Key (MK) polynomial time algorithms for the MK problem in new graph lasses? by using database te hniques. Can we use the latti e stru ture of to get new FX Re ently, KantØ and Nourine [12℄ have shown that is polynomial for M K shortest path betweenness relations of hordal and distan e hereditary graphs horn knowledge bases: Complexity and approximation. Artif. Intell., 64(1):131 7. Mitre Costa Dourado, John G. Gimbel, Jan Krato hvl, FÆbio Protti, and 100:75163, 1928. 10.1007/BF01448840.
University Press, 2002.
4. G. de Beauregard Robinson. The foundations of geometry. Mathemati al
exposiin relational databases: A latti e point of view. Dis rete Applied Mathemati s,
40(2):155185, 1992.
al report, Universitat PolitŁ ni a de Catalunya,
http://www5. JÆnos Demetrovi s, Leonid Libkin, and Ilya B. Mu hnik. Fun tional dependen ies
Vygen, J. (eds.) Resear h Trends in Combinatorial Optimization, pages 5764,
11. Peter L. Hammer and Alexander Kogan. Optimal ompression of propositional
Springer (Berlin and New York), 1999.
10. B. Ganter and R. Wille. Formal on ept analysis: Mathemati al foundations.
674, 1980.
17. Igna io M. Pelayo. On onvexity graphs. Te
hnimati s, 38:471485, 1971.
145, 1993.
tions. University of Toronto Press, 1952.
3. B. A. Davey and A. Priestley. Introdu tion to Latti es and Order. Cambridge
SIAM Journal on Algebrai and Dis rete Methods, 7:433444, 1986.
2. Va†ek ChvÆtal. Antimatroids, betweenness, onvexity. In Cook, W.J., LovÆz, L.,
ma3.up .es/users/pelayo/resear h/Denitions.pdf, 2004.
tween the CarathØodory, Helly, and Radon numbers. Pa i Journal of
MatheJayme Luiz Szwar ter. On the omputation of the hull number of a graph.
Disof Computer and System S ien es, 17(2):270 279, 1978.
16. Karl Menger. Untersu hungen ber allgemeine metrik. Mathematis he Annalen,
hypergraphs: A preliminary report. In ISAIM, 2012.
19. Despina Stasi, Robert H. Sloan, and Gyrgy TurÆn. Hydra formulas and dire ted
hull set in distan e-hereditary and hordal graphs. Submitted, 2012.
2019.
9. Martin Farber and Robert E. Jamison. Convexity in graphs and hypergraphs.
editor, Geometriae Dedi ata, vol 19, Ni3, pages 247270. springer, 1985.
12. M.M. KantØ and L. Nourine. Polynomial time algorithms for omputing a minimum
15. David Maier. Minimum overs in relational database model. J. ACM, 27(
The lattice of all betweenness relations: Structure and properties 325