NP-completeness in the gossip monoid

DOI10.1142/S0218196718500297zbMATH Open1498.20137arXiv1606.01026OpenAlexW2963266480MaRDI QIDQ4576008FDOQ4576008

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of semigroups
• On maximal subgroups of free idempotent generated semigroups.
• Free idempotent generated semigroups and endomorphism monoids of free \(G\)-acts.
• Subgroups of free idempotent generated semigroups need not be free.
• Maximal subgroups of free idempotent generated semigroups over the full linear monoid.
• Maximal subgroups of free idempotent-generated semigroups over the full transformation monoid.
• Graphs, networks and algorithms.
• Double Catalan monoids
• Title not available (Why is that?)
• A Cure for the Telephone Disease
• Lossy gossip and composition of metrics
• Gossips and telephones

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)