×

Unifying the representation of symmetric crossing families and weakly partitive families. (English) Zbl 1273.05233

Nešetřil, Jaroslav (ed.) et al., Extended abstracts of the 5th European conference on combinatorics, graph theory and applications, EuroComb’09, Bordeaux, France, September 7–11, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 34, 329-333 (2009).
Summary: The family of non-trivial minimizers of a symmetric submodular function is symmetric crossing, namely it is closed under the complementation of any member and under the intersection of its crossing members. The family of modules of a graph is weakly partitive, namely it is closed under the intersection, union, and difference of its overlapping members. Any symmetric crossing (resp. weakly partitive) family \(\mathcal{F}\subseteq 2^{X}\) has an \(O(|X|)\) space representation [W. Cunningham and J. Edmonds, Can. J. Math. 32, 734–765 (1980; Zbl 0442.05054)] (resp. [M. Chein et al., Discrete Math. 37, 35–50 (1981; Zbl 0478.05071); R. H. Möhring and F. J. Radermacher, in: Proceedings of the 19th workshop on annals of discrete mathematics. Amsterdam–New York–Oxford: North-Holland. 257–356 (1984; Zbl 0567.90073)]). In [the authors, Lect. Notes Comput. Sci. 4957, 492–503 (2008; Zbl 1136.68444)] we gave a general framework for representing any set family by a tree. This is a natural extension of the above mentioned result on symmetric crossing families. Here we show how our framework captures, in a non-trivial way, the above mentioned result on weakly partitive families aswell. Among the consequences, this is the first result generalizing both the modular decomposition of a graph and the structural behaviour of the minimizers of a symmetric submodular function.
For the entire collection see [Zbl 1239.05008].

MSC:

05E05 Symmetric functions and generalizations
05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Bui-Xuan, B.-M.; Habib, M., A representation theorem for union-difference families and application, (Proceedings of LATIN’08. Proceedings of LATIN’08, LNCS, 4957 (2008)), 492-503 · Zbl 1136.68444
[3] B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle. \(H\)to appear in Discrete Applied Mathematics: special issue of GROW; B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle. \(H\)to appear in Discrete Applied Mathematics: special issue of GROW · Zbl 1216.05153
[4] Chein, M.; Habib, M.; Maurer, M.-C., Partitive hypergraphs, Discrete Mathematics, 37, 1, 35-50 (1981) · Zbl 0478.05071
[5] Cunningham, W.; Edmonds, J., A combinatorial decomposition theory, Canadian Journal of Mathematics, 32, 734-765 (1980), Also in W. Cunningham’s thesis (1973) · Zbl 0442.05054
[6] Dinitz, E.; Karzanov, A.; Lomonosov, M., On the structure of a family of minimal weighted cuts in a graph, (Pridman, A., Studies in Discrete Optimization (1976)), 290-306, (in Russian)
[7] Edmonds, J.; Giles, R., A min-max relation for submodular functions on graphs, Annals of Discrete Mathematics, 1, 185-204 (1977)
[8] Möhring, R.; Radermacher, F., Substitution decomposition for discrete structures and connections with combinatorial optimization, Annals of Discrete Mathematics, 19, 257-356 (1984) · Zbl 0567.90073
[9] Oum, S.; Seymour, P., Approximating clique-width and branch-width, Journal on Combinatorial Theory Series B, 96, 4, 514-528 (2006) · Zbl 1114.05022
[10] Queyranne, M., Minimizing symmetric submodular functions, Mathematical Programming, 82, 1-2, 3-12 (1998) · Zbl 0949.90076
[11] Robertson, N.; Seymour, P., Graph minors X: Obstructions to tree-decomposition, Journal on Combinatorial Theory Series B, 52, 153-190 (1991) · Zbl 0764.05069
[12] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency (2003), Springer · Zbl 1041.90001
[13] Tedder, M.; Corneil, D.; Habib, M.; Paul, C., Simpler linear-time modular decomposition via recursive factorizing permutations, (Proceedings of ICALP’08. Proceedings of ICALP’08, LNCS, 5125 (2008)), 634-645 · Zbl 1153.68410
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.