A Compact Representation for Modular Semilattices and Its Applications
- PDF / 754,170 Bytes
- 29 Pages / 439.642 x 666.49 pts Page_size
- 49 Downloads / 201 Views
A Compact Representation for Modular Semilattices and Its Applications Hiroshi Hirai1 · So Nakashima1 Received: 27 July 2018 / Accepted: 18 November 2019 / © Springer Nature B.V. 2020
Abstract A modular semilattice is a semilattice generalization of a modular lattice. We establish a Birkhoff-type representation theorem for modular semilattices, which says that every modular semilattice is isomorphic to the family of ideals in a certain poset with additional relations. This new poset structure, which we axiomatize in this paper, is called a PPIP (projective poset with inconsistent pairs). A PPIP is a common generalization of a PIP (poset with inconsistent pairs) and a projective ordered space. The former was introduced by Barth´elemy and Constantin for establishing Birkhoff-type theorem for median semilattices, and the latter by Herrmann, Pickering, and Roddy for modular lattices. We show the (n) representation complexity and a construction algorithm for PPIP-representations of (∧, ∨)-closed sets in the product Ln of modular semilattice L. This generalizes the results of Hirai and Oki for a special median semilattice Sk . We also investigate implicational bases for modular semilattices. Extending earlier results of Wild and Herrmann for modular lattices, we determine optimal implicational bases and develop a polynomial time recognition algorithm for modular semilattices. These results can be applied to retain the minimizer set of a submodular function on a modular semilattice. Keywords Modular semilattice · Birkhoff representation theorem · Implicational base · Submodular function
1 Introduction The Birkhoff representation theorem says that every distributive lattice is isomorphic to the family of ideals in a poset (partially ordered set). This representation of a distributive lattice L is compact in the sense that the cardinality of the poset is at most the height
So Nakashima
so [email protected] Hiroshi Hirai [email protected] 1
Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1, Hongo, Bunkyoku, Tokyo, Japan
Order
of L, and consequently has brought numerous algorithmic successes in discrete applied mathematics. The family of all stable matchings in the stable matching problem forms a distributive lattice, and is compactly represented by a poset. Several algorithmic problems on stable matchings are elegantly solved by utilizing this poset representation [12]. The family of minimum s-t cuts in a network forms a distributive lattice. More generally, the family of minimizers of a submodular set function is a distributive lattice, and admits such a compact representation; see [8]. This fact grew up to theory of principal partitions of submodular systems, which is a general decomposition paradigm for graphs, matrices, and matroids [9, 23]. A canonical block-triangular form of a matrix by means of row and column permutations, known as the Dulmage-Mendelsohn decomposition (DM-decomposition), is obtained via a maxi
Data Loading...
