The influence of individuals in a network and its propagation is dealt with in several studies in the literature. A well-known model is the majority target set, in which if most of the neighbors of an individual in the network are influenced, then the individual is also influenced. Finding a majority target set of minimum size is an NP-hard problem for general graphs. This paper proposes a heuristic for this problem, which has faster runtimes and achieves better solution values than related works, both on small random instances and on large real social network graphs.

A knot in a directed graph G is a strongly connected subgraph Q of G with at least two vertices, such that no vertex in V(Q) is an in-neighbor of a vertex in V(G)\V(Q). Knots are important graph structures, because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Deadlock detection is correlated with the recognition of knot-free graphs as well as deadlock resolution is closely related to the Knot-Free Vertex Deletion (KFVD) problem, which consists of determining whether an input graph G has a subset S subseteq V(G) of size at most k such that G[V\S] contains no knot. Because of natural applications in deadlock resolution, KFVD is closely related to Directed Feedback Vertex Set. In this paper we focus on graph width measure parameterizations for KFVD. First, we show that: (i) KFVD parameterized by the size of the solution k is W[1]-hard even when p, the length of a longest directed path of the input graph, as well as kappa, its Kenny-width, are bounded by constants, and we remark that KFVD is para-NP-hard even considering many directed width measures as parameters, but in FPT when parameterized by clique-width; (ii) KFVD can be solved in time 2^{O(tw)} x n, but assuming ETH it cannot be solved in 2^{o(tw)} x n^{O(1)}, where tw is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set (dfv) is an upper bound for the size of a minimum knot-free vertex deletion set, we investigate parameterization by dfv and we show that (iii) KFVD can be solved in FPT-time parameterized by either dfv+kappa or dfv+p. Results of (iii) cannot be improved when replacing dfv by k due to (i).

Given a connected region in two-dimensional space where events of a certain kind occur according to a certain time-varying density, we consider the problem of setting up a network of autonomous mobile agents to detect the occurrence of those events and possibly record them in as effective a manner as possible. We assume that agents can communicate with one another wirelessly within a fixed communication radius, and moreover that initially no agent has any information regarding the event density. We introduce a new distributed algorithm for agent control based on the notion of an execution mode, which essentially lets each agent roam the target region either at random or following its local view of a density-dependent gradient. Agents can switch back and forth between the two modes, and the precise manner of such changes depends on the setting of various parameters that can be adjusted as a function of the application at hand. We provide simulation results on some synthetic applications especially designed to highlight the algorithm's behavior relative to the possible execution modes.

We study perfect matchings in graphs that have the two properties of being robust as well as recoverable; where robust means that the failure of a set of not too many edges of can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, has a perfect matching for which the symmetric difference of and is small. We establish the hardness of several related algorithmic problems and identify some tractable cases. Among others we show the hardness of the well known matching preclusion number of a graph. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 210–213 2015

A set of vertices C in a graph is convex if it contains all vertices which lie on shortest paths between vertices in C. The convex hull of a set of vertices S is the smallest convex set containing S. The hull number $h(G)$ of a graph G is the smallest cardinality of a set of vertices whose convex hull is the vertex set of G. For a connected triangle-free graph G of order n and diameter d at least 4, we prove that $h(G)\leq(n-d+3)/3$ if G has minimum degree at least 3 and that $h(G)\leq2(n-d+5)/7$, if G is cubic. Furthermore for a connected graph G of order n, girth g at least 5, minimum degree at least 2, and diameter d, we prove $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.

Abstract A graph G is a grid intersection graph if G is the intersection graph of ℋ︁ ∪ ℐ, where ℋ︁ and ℐ are, respectively, finite families of horizontal and vertical linear segments in the plane such that no two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) The family ℋ︁ ∪ ℐ is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl, we observe that when a bipartite graph G = (U ∪ W, E) with minimum degree at least two is a grid intersection graph, then there exists a normalized representation of G on the (r × s)‐grid for r = |U| and s = |W|, that is, a representation in which all end points of segments have integer‐valued coordinates belonging to {(x, y) ∈ N × N | 1 ≤ y ≤ r, 1 ≤ x ≤ s} and the representative segment of each vertex lies on a distinct horizontal or vertical line. A natural problem, with potential applications to circuit layout, is the following: among all the possible normalized representations of G, find a representation ℛ such that the sum of the lengths of the segments in ℛ is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 187–193 2004