Abstract Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity () for several graph theoretic problems in : Maximum ‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width () and consequently—as is a special case of —by . However, the proposed novel algorithms allow for improving the computational complexity from time —where and denote, respectively, the number of vertices and edges in the input graph—to time which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.

List union-free families are basic combinatorial structures that appear in different application scenarios, most notably in one-bit compressed sensing. In this paper, we study algorithms for the construction of list union-free families and we provide bounds on the parameters of these families that substantially affect the complexity of the algorithms that utilize them.

In this paper, we study upper bounds on the minimum length of frameproof codes introduced by Boneh and Shaw [3] to protect copyrighted materials. A q-ary (k,n)-frameproof code of length t is a t×n matrix having entries in {0,1,…,q−1} and with the property that for any column c and any other k columns, there exists a row where the symbols of the k columns are all different from the corresponding symbol (in the same row) of the column c. In this paper, we show the existence of q-ary (k,n)-frameproof codes of length $t = O\left( {\frac{{{k^2}}}{q}\log n} \right)$ for q ≤ k, using the Lovász Local Lemma, and of length $t = O\left( {\frac{{{k^2}}}{{\log \left( {q/k} \right)}}\log \left( {n/k} \right)} \right)$ for q > k using the expurgation method. Remarkably, for the practical case of q ≤ k our findings give codes whose length almost matches the lower bound $\Omega \left( {\frac{{{k^2}}}{{q\log k\log n}}} \right)$ on the length of any q-ary (k,n)-frameproof code and, more importantly, allow us to derive an algorithm of complexity O(tn2) for the construction of such codes.

Abstract We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and $$\ell $$ ℓ , is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most $$\ell $$ ℓ nodes? We consider several parameters associated with the input, including the bounds k and $$\ell $$ ℓ , the maximum node degree $$\Delta $$ Δ , the number $$\zeta $$ ζ of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

We consider a population of interconnected individuals that, with respect to a piece of information, at each time instant can be subdivided into three (time‐dependent) categories: agnostics, influenced, and evangelists. A dynamical process of information diffusion evolves among the individuals of the population according to the following rules. Initially, all individuals are agnostic. Then, a set of people is chosen from the outside and convinced to start evangelizing, that is, to start spreading the information. When a number of evangelists, greater than a given threshold, communicate with a node v, the node v becomes influenced, whereas, as soon as the individual v is contacted by a sufficiently much larger number of evangelists, it is itself converted into an evangelist and consequently it starts spreading the information. The question is: How to choose a bounded cardinality initial set of evangelists so as to maximize the final number of influenced individuals? We prove that the problem is hard to solve, even in an approximate sense. On the positive side, we present exact polynomial time algorithms for trees and complete graphs. For general graphs, we derive exact parameterized algorithms. We also study the problem when the objective is to select a minimum number of evangelists capable of influencing the whole network. Our motivations to study these problems come from the areas of Viral Marketing and spread of influence in social networks. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 346–357 2018

Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. We study the problem of choosing a small set of initial spreaders so as to maximize the final number of nodes that become aware of the information.

We study the influence diffusion problem in online social networks. Formally, given a network represented by a directed graph G = (V,E), we consider a process of influence diffusion in G that proceeds as follows: Initially only the vertices of a given S ⊆ V are influenced; subsequently, at each round, the set of influenced vertices is augmented by all the vertices in the network that have a sufficiently large number of already influenced incoming neighbors. The question is to find a small subset of vertices that can influence the whole network (target set). This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known to be hard to approximate within a factor of 2log1--ϵn, for any ϵ > 0, and n = |V |.

The one-to-all personalized broadcast problem in an interconnection network can be optimally solved with respect to both the time and the number of transmissions if it is possible to construct an optimally balanced spanning tree of the network which is also a shortest path tree. We give an algorithm to construct an optimally balanced spanning tree of the star network which is also a shortest path tree. Our result is optimal and improves on that of Chen et al. (1996) and Day and Tripathi (1994).

Collective communication operations play an important role in message-passing systems and have been extensively investigated. We study two widely used collective communication operations: gossiping and all-to-all personalized communication. We assume the multiport postal model of communication that seems particularly suited for developing fast and portable algorithms on current technology parallel computers. Unlike most of the previous work on the subject, we assume that processors communicate by sending messages of limited size. Indeed, when the maximum size of a message is fixed, the number of rounds required by a communication algorithm gives a realistic measure of the performance of the algorithm. We provide an optimal algorithm for the gossiping operation and an almost-optimal algorithm for the all-to-all personalized communication operation. © 1998 John Wiley & Sons, Inc. Networks 31:67–79, 1998

Gossiping is the process of information diffusion in which each node of a network holds a packet that must be communicated to all other nodes in the network. We consider the problem of gossiping in communication networks under the restriction that communicating nodes can exchange up to a fixed number p of packets at each round. In the first part of the paper we study the extremal case p=1 and we exactly determine the optimal number of communication rounds to perform gossiping for several classes of graphs, including Hamiltonian graphs and complete k-ary trees. For arbitrary graphs we give asymptotically matching upper and lower bounds. We also study the case of arbitrary p and we exactly determine the optimal number of communication rounds to perform gossiping under this hypothesis for complete graphs, hypercubes, rings, and paths. Finally, we investigate the problem of determining sparse networks in which gossiping can be performed in the minimum possible number of rounds.

Polling is the process in which an issuing node of a communication network (polling station) broadcasts a query to every other node in the network and waits to receive a unique response from each of them. Polling can be thought of as a combination of broadcasting and gathering and finds wide applications in the control of distributed systems. In this paper, we consider the problem of polling in minimum time. We give a general lower bound on the minimum number of time units to accomplish polling in any network and we present optimal polling algorithms for several classes of graphs, including hypercubes and recursively decomposable Cayley graphs.

In this paper we consider the Supercube, a new interconnection network derived from the hypercube. The Supercube, introduced by A. Sen (1989), has the same diameter and connectivity as a Hypercube but can be realized for any number of nodes, not only powers of 2. We study the Supercube's ability to execute parallel programs, using graph-embedding techniques. We show that complete binary trees and bidimensional meshes (with a side length power of 2) are spanning subgraphs of the Supercube. We then prove that the Supercube is Hamiltonian and, when the number of nodes is not a power of 2, it contains all cycles of length greater than 3 as subgraphs.>

Abstract Broadcasting is the process of disseminating a message originated at one node of a network to all other nodes. In this paper, we consider the problem of broadcasting reliably in the hypercube in presence of either transmission or link failures. We propose broadcasting protocols under various assumptions on the communication model. Our broadcasting protocols make use of Rabin's Information Dispersal Algorithm. © 1993 by John Wiley & Sons, Inc.