No Access

NP-Completeness in the gossip monoid

Peter Fenner

School of Mathematics, University of Manchester, Manchester M13 9PL, England

E-mail Address: Peter.Fenner@postgrad.manchester.ac.uk

Search for more papers by this author

Marianne Johnson

School of Mathematics, University of Manchester, Manchester M13 9PL, England

E-mail Address: Marianne.Johnson@maths.manchester.ac.uk

Search for more papers by this author

, and

Mark Kambites

School of Mathematics, University of Manchester, Manchester M13 9PL, England

E-mail Address: Mark.Kambites@manchester.ac.uk

Search for more papers by this author

https://doi.org/10.1142/S0218196718500297Cited by:3 (Source: Crossref)

Abstract

Gossip monoids form an algebraic model of networks with exclusive, transient connections in which nodes, when they form a connection, exchange all known information. They also arise naturally in pure mathematics, as the monoids generated by the set of all equivalence relations on a given finite set under relational composition. We prove that a number of important decision problems for these monoids (including the membership problem, and hence the problem of deciding whether a given state of knowledge can arise in a network of the kind under consideration) are NP-complete. As well as being of interest in their own right, these results shed light on the apparent difficulty of establishing the cardinalities of the gossip monoids: a problem which has attracted some attention in the last few years.

Communicated by S. Margolis

Keywords:

AMSC: Primary 20M99, Secondary 68Q17

References

1. B. Baker and R. Shostak, Gossips and telephones, Discrete Math. 2 (1972) 191–193. Google Scholar
2. M. Brittenham, S. W. Margolis and J. Meakin, Subgroups of the free idempotent generated semigroups need not be free, J. Algebra 321(10) (2009) 3026–3042. Web of Science, Google Scholar
3. A. E. Brouwer, J. Draisma and B. J. Frenk, Lossy gossip and composition of metrics, Discrete Comput. Geom. 53 (2015) 890–913. Web of Science, Google Scholar
4. A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Vol. I, Mathematical Surveys, Vol. 7 (American Mathematical Society, Providence, R.I., 1961). Google Scholar
5. I. Dolinka and R. Gray, Maximal subgroups of free idempotent generated semigroups over the full linear monoid, Trans. Amer. Math. Soc. 366(1) (2014) 419–455. Web of Science, Google Scholar
6. B. Frenk, Tropical varieties, maps and gossip, Ph.D. thesis, Eindhoven University of Technology (2013). Google Scholar
7. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to NP-Completeness (W.H. Freeman and Company, San Francisco, 1979). Google Scholar
8. R. Gray and N. Rus̆kuc, On maximal subgroups of free idempotent generated semigroups, Israel J. Math. 189 (2012) 147–176. Web of Science, Google Scholar
9. R. Gray and N. Rus̆kuc, Maximal subgroups of free idempotent-generated semigroups over the full transformation monoid, Proc. Lond. Math. Soc. 104(5) (2012) 997–1018. Web of Science, Google Scholar
10. J. A. Green, On the structure of semigroups, Ann. Math. 54 (1951) 163–172. Web of Science, Google Scholar
11. A. Hajnal, E. C. Milner and E. Szemeredi, A cure for the telephone disease, Canad. Math. Bull. 15 (1972) 447–450. Web of Science, Google Scholar
12. D. Jüngnickel, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics, Vol. 5 (Springer, Heidelberg, 2013). Google Scholar
13. V. Mazorchuk and B. Steinberg, Double Catalan monoids, J. Algebraic Combin. 36(3) (2012) 333–354. Web of Science, Google Scholar
14. R. Tijdeman, On a telephone problem, Nieuw Arch. Wiskd. 19(3) 1971 188–192. Google Scholar
15. D. Yang, I. Dolinka and V. Gould, Free idempotent generated semigroups and endomorphism monoids of free $G$ -acts, J. Algebra 429 (2015) 133–176. Web of Science, Google Scholar