NP-completeness in the gossip monoid

DOI10.1142/S0218196718500297MaRDI QIDQ4576008zbMATH OpenOpenAlexFDO

Authors Peter Fenner, Marianne Johnson, Mark Kambites

Publication date 12 July 2018

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.01026

zbMATH Keywords

computational complexitynetworkssemigroup theorygossip

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Free semigroups, generators and relations, word problems (20M05)

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.

Recommendations

• The logic of gossiping
• scientific article; zbMATH DE number 866663
• Communication complexity of gossiping by packets
• Communication complexity of gossiping by packets
• A survey of gossiping and broadcasting in communication networks

Cites work

• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3358479 (Why is no real title available?)
• A Cure for the Telephone Disease
• Double Catalan monoids
• Free idempotent generated semigroups and endomorphism monoids of free \(G\)-acts.
• Gossips and telephones
• Graphs, networks and algorithms.
• Lossy gossip and composition of metrics
• Maximal subgroups of free idempotent generated semigroups over the full linear monoid.
• Maximal subgroups of free idempotent-generated semigroups over the full transformation monoid.
• On maximal subgroups of free idempotent generated semigroups.
• On the structure of semigroups
• Subgroups of free idempotent generated semigroups need not be free.

Cited in

(3)

• Lossy gossip and composition of metrics
• Identities of the stylic monoid
• Identities in unitriangular and gossip monoids

This page was built for publication: NP-completeness in the gossip monoid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4576008)