Search

We address the problem of finding an arborescence of minimum total edge weight rooted at a given vertex in a directed, edge-weighted graph. If the arborescence must span all vertices the problem is solvable in polynomial time, but the non-spanning version is NP-hard. We propose reduction rules which determine vertices that are required or can be excluded from optimal solutions, a modification of Edmonds algorithm to construct arborescences that span a given set of selected vertices, and embed this procedure into an iterated local search for good vertex selections. Moreover, we propose a cutset-based integer linear programming formulation, provide different linear relaxations to reduce the number of variables in the model and solve the reduced model using a branch-and-cut approach. We give extensive computational results showing that both the heuristic and the exact methods are effective and obtain better solutions on instances from the literature than existing approaches, often in much less time.

This paper considers broadcast communications or information dissemination in Fixed-Schedule Dynamic Networks (FSDNs). It shows that the notion of spanning arborescences, commonly used in static networks, is not applicable in FSDNs. This paper then introduces two new concepts on spanning arborescences: (i) ${\boldsymbol{t}}$ -arborescence – an arborescence in which all edges have contact schedules, and (ii) ${\boldsymbol{tv}}$ -arborescence – a ${\boldsymbol{t}}$ -arborescence that requires time-ordered edges to establish a communication scenario. The paper discusses properties of these spanning arborescences, and proposes two novel methods, TA-to-TVA and A-to-TVA, that utilize Tutte's Matrix-Tree theorem to enumerate all ${\boldsymbol{tv}}$ -arborescences. Next, it considers edges in FSDNs with a probability of failure, and proposes two new broadcast reliability metrics. Then, this paper shows how to use ${\boldsymbol{tv}}$ -arborescences to compute these reliability metrics. Our simulations with ten arbitrary FSDNs show that A-to-TVA, which generates ${\boldsymbol{tv}}$ -arborescences from static arborescences, is more time efficient than TA-to-TVA, which enumerates them from ${\boldsymbol{t}}$ -arborescences. They also show that nodes having more ${\boldsymbol{tv}}$ -arborescences do not always yield a higher broadcast reliability.

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates: 1) shortest distances from a root to the other vertices and 2) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one. In this paper, we propose a novel Steiner SLT construction method called Steiner SLT (SALT), which is efficient and has the tightest bound over all the state-of-the-art general-graph SLT algorithms. Applying SALT to Manhattan space offers a smooth tradeoff between rectilinear Steiner minimum tree and rectilinear Steiner minimum arborescence for VLSI routing. The adaption also reduces the time complexity from ${O}$ ( ${n} ^{2}$ ) to ${O}$ ( ${n}$ log ${n}$ ). Besides, several effective post-processing methods, including safe refinement and shallowness-constrained edge substitution, are proposed to further improve the result. The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

Square-root topology is a recently emerged subfield describing a class of insulators and superconductors whose topological nature is only revealed upon squaring their Hamiltonians, i.e., the finite energy edge states of the starting square-root model inherit their topological features from the zero-energy edge states of a known topological insulator/superconductor present in the squared model. Focusing on one-dimensional models, we show how this concept can be generalized to $2^n$-root topological insulators and superconductors, with $n$ any positive integer, whose rules of construction are systematized here. Borrowing from graph theory, we introduce the concept of arborescence of $2^n$-root topological insulators/superconductors which connects the Hamiltonian of the starting model for any $n$, through a series of squaring operations followed by constant energy shifts, to the Hamiltonian of the known topological insulator/superconductor, identified as the source of its topological features. Our work paves the way for an extension of $2^n$-root topology to higher-dimensional systems., 19 pages, 15 figures

International audience; Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the spanning arborescence packing problem to a matroid-based arborescence packing problem and gave a necessary and sufficient condition for the existence of a packing and a polynomial-time algorithm.In this paper, a generalization of this latter problem – the polymatroid-based arborescence packing problem – is considered. Two problem settings are formulated: an unsplittable version and a splittable version. The unsplittable version is shown to be strongly NP-complete. Whereas, the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, can be solved in strongly polynomial time. For convenience, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for the splittable version.

We consider the problem of optimal propagation of cascades in a network, where the propagation process depends on the values that a decision-maker assigns to the network and independent influence rates. Assuming that there are costs associated with changing the values of these rates, we investigate the question of resource allocation that minimizes the time by which the cascading process reaches all nodes. To this end, we propose a model that represents the cascading process in the network as a continuous time Markov chain (CTMC). We show how the propagation problem can be framed as an eigenvalue optimization problem on the generator of the CTMC. In turn, this problem is successively transformed into a maximum minimum cut problem and into a generalized maximum flow problem on a linearly-sized auxiliary graph. Therefore, the optimization problem can be solved in strongly polynomial time in terms of the size of the network. In addition, whenever there are no preexisting influence rates, the problem can also be transformed into the problem of finding a minimum spanning arborescence on a similar auxiliary graph. In this setting the optimal solution provides a hierarchy that classifies the nodes in terms of their importance to the cascade propagation.

Let us be given a rooted digraph D = ( V + s , A ) with a designated root vertex s . Edmonds' seminal result [Edmonds, J., Edge-disjoint branchings , in: B. Rustin (ed.) Combinatorial Algorithms, Academic Press, New York, 91–96 (1973] states that D has a packing of k spanning s -arborescences if and only if D has a packing of k ( s , t )-paths for all t ∈ V , where a packing means arc-disjoint subgraphs. Let M be a matroid on the set of arcs leaving s . A packing of ( s , t )-paths is called M -based if their arcs leaving s form a base of M while a packing of s -arborescences is called M -based if, for all t ∈ V , the packing of ( s , t )-paths provided by the arborescences is M -based. Durand de Gevigney, Nguyen and Szigeti proved in [Durand de Gevigney, O., V.H. Nguyen, and Z. Szigeti, Matroid-based packing of arborescences , SIAM J. Discrete Math., 27 (2013), 567–574] that D has an M -based packing of s -arborescences if and only if D has an M -based packing of ( s , t )-paths for all t ∈ V . Berczi and Frank conjectured that this statement can be strengthened in the sense of Edmonds' theorem such that each s -arborescence is required to be spanning. Specifically, they conjectured that D has an M -based packing of spanning s -arborescences if and only if D has an M -based packing of ( s , t )-paths for all t ∈ V . We disprove this conjecture in its general form and we prove that the corresponding decision problem is NP-complete. However, we prove that the conjecture holds for several fundamental classes of matroids, such as graphic matroids and transversal matroids.

We consider a problem arising in the design of ad-hoc wireless sensor networks. Given a connected bidirectional digraph with n sensors and a fixed sink, the p-arborescence star problem is the problem of clustering the sensors into p disjoint subsets and defining a directed backbone that spans the sink and all p cluster-heads, one for each cluster. The overall objective of the problem is to minimize the sum of intra and inter-cluster costs. We introduce and compare formulations based on directed cutset constraints and multicommodity flow variables. Valid inequalities to strengthen the models are also given. To solve these models, we develop efficient cutting-plane methods. We carry out extensive computational experiments and comparisons to illustrate the performance of our methods.

Broadcasting in a computer network is a method of transferring a message to all recipients simultaneously. It is common in this situation to use a tree with many leaves to perform the broadcast, as internal nodes have to forward the messages received, while leaves are only receptors. We consider the subjacent problem of, given a directed graph D, finding a spanning arborescence of D, if one exists, with the maximum number of leaves. In this paper, we concentrate on the class of rooted directed acyclic graphs, for which the problem is known to be MaxSNP-hard. A 2-approximation was previously known for this problem on this class of directed graphs. We improve on this result, presenting a 3/2-approximation. We also adapt a result for the undirected case and derive an inapproximability result for the vertex-weighted version of Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs.

In this work, we introduce profit-oriented capacitated ring arborescence problems and present exact and heuristic algorithms. These combinatorial network design problems ask for optimized bi-level networks taking into account arc costs and node profits. Solutions combine circuits on the inner level with arborescences on the outer level of the networks. We consider the prize-collecting, the budget-constrained and the target-profit models and develop corresponding exact branch-and-cut algorithms based on mixed-integer formulations and valid inequalities. Iterated local search heuristics based on the exploration of problem-specific neighborhoods are elaborated to strengthen the upper bounds. For a set of hard literature derived instances with up to 51 nodes, we provide computational results which give evidence for the efficiency of the proposed approaches. Furthermore, we extensively analyze the performance of our methods, the obtained solution networks and the impact of the cutting planes on the obtained lower bounds.

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a cen- tral pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.

The minimum cost dominating tree problem is a recently introduced NP-hard problem, which consists of finding a tree of minimal cost in a given graph, such that for every node of the graph, the node or one of its neighbours is in the tree. We present an exact solution framework combining a primal–dual heuristic with a branch-and-cut approach based on a transformation of the problem into a Steiner arborescence problem with an additional constraint. The effectiveness of our approach is evaluated on testbeds proposed in literature containing instances with up to 500 nodes. Our framework manages to solve all but four instances from literature to proven optimality within 3 h (most of them in a few seconds). We provide optimal solution values for 69 instances from literature for which the optimal solution was previously unknown.

In this paper, we study the location aware influence maximization problem, which finds a seed set to maximize the influence spread on targeted users for a given query. In particular, we consider users who have geographical preferences on queries as targeted users. One challenge of the problem is how to find the targeted users and compute their preferences efficiently for given queries. To address this challenge, based on the R-tree, we devise a PR-tree index structure, in which each tree node stores the location and information of users geographical preferences. By traversing the PR-tree from the root in depth-first order, we can efficiently find the targeted users. Another challenge of the problem is to devise an algorithm for efficient seeds selection. To solve this challenge, we adopt the maximum influence arborescence (MIA) model to approximate the influence spread, and propose an efficient community-based seeds selection (CSS) algorithm. The proposed CSS algorithm finds seeds efficiently by constructing the PR-tree based indexes offline which precompute users community based influences, and preferentially computing the marginal influences of those who would be selected as seeds with high probability online. In particular, we propose a community detection algorithm which first computes the social influence based similarities by the MIA model and then adopts the spectral clustering algorithm to find optimal communities of the social network. Experimental results on real-world datasets collected from DoubanEvent demonstrate our proposed algorithm has superiority as compared to several state-of-the-art algorithms in terms of efficiency, while keeping large influence spread.

In real social networks, it is often the case that opposite opinions, ideas, products, or innovations are propagating simultaneously. Although the competitive influence problem has been extensively studied, existing works neglect the fact that the location information can play an important role in influence propagation. In this paper, we study the location-aware influence blocking maximization (LIBM) problem, which aims to find a positive seed set to maximize the blocked negative influence for a given query region. In order to overcome low efficiency of the greedy algorithm, we propose two heuristic algorithms LIBM-H and LIBM-C based on the quadtree index and the maximum influence arborescence structure. Experimental results on real-world datasets show that both LIBM-H and LIBM-C are able to achieve a matching blocking effect to the greedy algorithm and often better than other heuristic algorithms, whereas they are several orders of magnitude faster than the greedy algorithm.

This Letter first proposes an algorithm for compressing the sets of the similar images with priorities. The proposed algorithm includes four modules, i.e. priority assigned, depth- and priority-constrained minimum arborescence generation, disparity reduction, and residue coding. Experimental results demonstrate that the proposed algorithm can effectively compress the similar images with priorities, and achieves similar rate-distortion performance to the state-of-the-art image set compression algorithm which has no constraints of depth and priority.

This paper studies the multi-vehicle task assignment problem where several dispersed vehicles need to visit a set of target locations in a time-invariant drift field while trying to minimize the total travel time. Using optimal control theory, we first design a path planning algorithm to minimize the time for each vehicle to travel between two given locations in the drift field. The path planning algorithm provides the cost matrix for the target assignment, and generates routes once the target locations are assigned to a vehicle. Then, we propose several clustering strategies to assign the targets, and we use two metrics to determine the visiting sequence of the targets clustered to each vehicle. Mainly used to specify the minimum time for a vehicle to travel between any two target locations, the cost matrix is obtained using the path planning algorithm, and is in general asymmetric due to time-invariant currents of the drift field. We show that one of the clustering strategies can obtain a min-cost arborescence of the asymmetric target vehicle graph where the weight of a directed edge betweentwo vertices is the minimum travel time from one vertex to the other respecting the orientation. Using tools from graph theory, a lower bound on the optimal solution is found, which can be used to measure the proximity of a solution from the optimal. Furthermore, by integrating the target clustering strategies with the target visiting metrics, we obtain several task assignment algorithms. Among them, two algorithms guarantee that all the target locations will be visited within a computable maximal travel time, which is at most twice of the optimal when the cost matrix is symmetric. Finally, numerical simulations show that the algorithms can quickly lead to a solution that is close to the optimal.

In this paper, we study the location-aware targeted influence maximization problem in social networks, which finds a seed set to maximize the influence spread over the targeted users. In particular, we consider those users who have both topic and geographical preferences on promotion products as targeted users. To efficiently solve this problem, one challenge is how to find the targeted users and compute their preferences efficiently for given requests. To address this challenge, we devise a TR-tree index structure, where each tree node stores users' topic and geographical preferences. By traversing the TR-tree in depth-first order, we can efficiently find the targeted users. Another challenge of the problem is to devise algorithms for efficient seeds selection. We solve this challenge from two complementary directions. In one direction, we adopt the maximum influence arborescence (MIA) model to approximate the influence spread, and propose two efficient approximation algorithms with 1−1/e approximation ratio, which prune some candidate seeds with small influences by precomputing users' initial influences offline and estimating the upper bound of their marginal influences online. In the other direction, we propose a fast heuristic algorithm to improve efficiency. Experiments conducted on real-world data sets demonstrate the effectiveness and efficiency of our proposed algorithms.

Bad information propagation in online social networks (OSNs) can cause undesirable effects. The opposite good information propagating competitively with bad information can restrain the propagation of bad information. In this paper, we address the Influence Blocking Maximization (IBM) problem aiming to find a set of influential people initiating good information propagation to maximize the blocking effect on the bad information propagation in OSNs. The problem is studied on two competitive propagation models describing competitive propagation processes in two classic situations in OSNs. Two models are derived from the Independent Cascade Model (ICM). Greedy algorithms for IBM problem under two competitive propagation models are slow and not scalable. Thus, we design two heuristics CMIA-H and CMIA-O based on the maximum influence arborescence (MIA) structure to efficiently solve the IBM problem under two competitive propagation models, respectively. Extensive experiments are conducted on real-world and synthetic datasets to compare the proposed algorithms with the greedy algorithms and other baseline heuristics. The results demonstrate that both CMIA-H and CMIA-O achieve matching influence blocking performance to the greedy algorithms and consistently outperform other baseline heuristics, while they are several orders of magnitude faster than the greedy algorithms.

A digraph is n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is ( n + k − 1 ) -unavoidable. We then prove that every oriented tree of order n ( n ≥ 2 ) with k leaves is ( 3 2 n + 3 2 k − 2 ) -unavoidable and ( 9 2 n − 5 2 k − 9 2 ) -unavoidable, and thus ( 21 8 n − 47 16 ) -unavoidable. Finally, we prove that every oriented tree of order n with k leaves is ( n + 144 k 2 − 280 k + 124 ) -unavoidable.

In this issue, we consider the location-aware targeted influence blocking maximization (LTIBM) problem, which plays a very important role in viral marketing and rumor control. LTIBM aims to find a set of positive seeds in a given social network to block the influence propagation of negative seeds over the targeted nodes located in a given region and having a preference on a given topic set as much as possible. We devise a simulation-based greedy algorithm based on monotone and submodular characteristics of influence function under the homogeneous independent cascade model. To improve the efficiency of the greedy algorithm, we propose LTIBM-H, a heuristic algorithm based on QT-tree and maximum influence arborescence (MIA). Experimental results show that the proposed LTIBM-H algorithm can achieve matching the blocking effect to the greedy algorithm and often performs better in terms of effectiveness than other baseline algorithms, while LTIBM-H is four orders of magnitude faster than the greedy algorithm.

Given a matroid M defined by an independence oracle on a ground set E, the Matroid Base Game is played by two players: the defender chooses a basis B and (simultaneously) the attacker chooses an element $$e \in E$$ . The attacker incurs a cost c(e) for choosing an element e, and if $$e \in B$$ then there is a probability p(e) that the attacker will detect the defender. The defender has to find a bases-selection strategy that minimizes the average probability of being detected. The attacker has to find a probabilistic selection strategy that maximizes the average detection probability minus its average cost. An algorithm to compute Nash-equilibrium mixed strategies was given in Szeszler (Math Program 161:347–364, 2016). Its time complexity is $$O(|E|^{10} IO)$$ , where IO is the time that it takes one call to the independence oracle. Here we present an algorithm that requires $$O(|E|^6 IO)$$ time. For graphic matroids, i.e., when the defender chooses a spanning tree in a graph $$G=(V,E)$$ , and the attacker chooses an edge, we give an algorithm that takes $$O(|V|^4 |E|^{1/2})$$ time. This type of game is extended to common bases of two matroids. For this case we give a strongly polynomial algorithm, settling a question that was left open in Szeszler (2016). We also treat the case when the defender chooses a rooted arborescence in a directed graph $$D=(V,\mathscr {A})$$ , and the attacker chooses an arc, we use this structure to give an algorithm that requires $$O(|V||\mathscr {A}|^3 \log (|V|^2/|\mathscr {A}|) \log |\mathscr {A}|)$$ time.

It is of significance to identify the source of malicious information in social networks, since this information diffusion is already a problem, which can seriously affect social stability. In this paper, we develop a propagation path based approach where the estimator of information source is chosen to be the root node associated with the propagation path that most likely leads to the monitored state of network. When the information diffusion process follows the Susceptible-Infected (SI) model and satisfying the instant forwarding hypothesis, we proved that the source estimator we proposed is the root node of the network shortest arborescence. Finally, multiple simulations on networks with different structure show that our method outperforms existing algorithms.

Influence blocking maximization (IBM) is a key problem for viral marketing in competitive social networks. Although the IBM problem has been extensively studied, existing works neglect the fact that the location information can play an important role in influence propagation. In this paper, we study the location-based seeds selection for IBM problem, which aims to find a positive seed set in a given query region to block the negative influence propagation in a given block region as much as possible. In order to overcome the low efficiency of the simulation-based greedy algorithm, we propose a heuristic algorithm IS-LSS and its improved version IS-LSS+, both of which are based on the maximum influence arborescence structure and Quadtree index, while IS-LSS+ further improves the efficiency of IS-LSS by using an upper bound method and Quadtree cell lists. The experimental results on real-world datasets demonstrate that our proposed algorithms are able to achieve matching blocking effect to the greedy algorithm as the increase in the number of positive seeds and often better than other heuristic algorithms, whereas they are four orders of magnitude faster than the greedy algorithm. 2013 IEEE. This work was supported in part by the National Natural Science Foundation of China under Grant 61572459 and Grant 61672180, in part by the Basic Scientific Research Project of Heilongjiang Education Department under Grant 135309469, and in part by the Teaching and Scientific Research Project of Qiqihar University under Grant 2016086 and Grant 201803. Scopus 2-s2.0-85062982497

International audience; Edmonds' arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a characterization in terms of matroid intersection. Since these fundamental results, intensive research has been done for understanding and extending these results. In this paper we shall extend the second characterization to the setting of reachability-based packing of arborescences. The reachability-based packing problem was introduced by Cs. Kiraly as a common generalization of two different extensions of the spanning arborescence packing problem, one is due to Kamiyama, Katoh, and Takizawa, and the other is due to Durand de Gevigney, Nguyen, and Szigeti. Our new characterization of the arc sets of reachability-based packing in terms of matroid intersection gives an efficient algorithm for the minimum weight reachability-based packing problem, and it also enables us to unify further arborescence packing theorems and Edmonds' matroid intersection theorem. For the proof, we also show how a new class of matroids can be defined by extending an earlier construction of matroids from intersecting submodular functions to bi-set functions based on an idea of Frank.

We propose a generalized framework for influence maximization in large-scale, time evolving networks. Many real-life influence graphs such as social networks, telephone networks, and IP traffic data exhibit dynamic characteristics, e.g., the underlying structure and communication patterns evolve with time. Correspondingly, we develop a dynamic framework for the influence maximization problem, where we perform effective local updates to quickly adjust the top-k influencers, as the structure and communication patterns in the network change. We design a novel N-Family method (N=1, 2, 3, …) based on the maximum influence arborescence (MIA) propagation model with approximation guarantee of (1 − 1/e). We then develop heuristic algorithms by extending the N-Family approach to other information propagation models (e.g., independent cascade) and influence maximization algorithms (e.g., CELF, reverse reachable sketch). Based on a detailed empirical analysis over several real-world, dynamic, and large-scale networks, we find that our proposed solution, N-Family improves the updating time of the top-k influencers by 1 ∼ 2 orders of magnitude, compared to existing algorithms, while ensuring similar memory usage and influence spreads.

The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph $$D=(V,A)$$D=(V,A) with a designated root node $$r\in V$$rźV and arc-costs $$c:A\rightarrow \mathbb {R}$$c:AźR, find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give solves a weighted version as well, in which a nonnegative weight function $$w:A\rightarrow \mathbb {R}_+$$w:AźR+ (unrelated to c) is also given, and we want to find a subset H of the arc set such that H intersects every minimum c-cost r-arborescence, and $$w(H)=\sum _{a\in H}w(a)$$w(H)=źaźHw(a) is minimum. The running time of the algorithm is $$O(n^3T(n,m))$$O(n3T(n,m)), where n and m denote the number of nodes and arcs of the input digraph, and T(n, m) is the time needed for a minimum $$s-t$$s-t cut computation in this digraph. A polyhedral description is not given, and seems rather challenging.

In this letter, a novel synthetic aperture radar (SAR) image registration method, including two operators for feature detection and arborescence network matching (ANM) for feature matching, is proposed. The two operators, namely, SAR scale-invariant feature transform (SIFT) and R-SIFT, can detect corner points and texture points in SAR images, respectively. This process has an advantage of preserving two types of feature information in SAR images simultaneously. The ANM algorithm has a two-stage process for finding matching pairs. The backbone network and the branch network are successively built. This ANM algorithm combines feature constraints with spatial relations among feature points and possesses a larger number of matching pairs and higher subpixel matching precision than the original version. Experimental results on various SAR images show that the proposed method provides superior performance than other approaches investigated.

Influence maximization is an important problem in social networks. Bharathi et al. (Competitive influence maximization in social networks, pp 306---311, 2007) conjectured that this problem is $${{\mathcal {N}}}{{\mathcal {P}}}$$NP-hard on arborescence directed into a root. In this short note, we show that the conjecture is true for the independent cascade (IC) model, which is the most studied model in the literature specifying how each node influences other nodes. Therefore, assuming $${\mathcal {P}}\ne {{\mathcal {N}}}{{\mathcal {P}}}$$PźNP, there exists no polynomial-time algorithm for the influence maximization problem under the IC model on arborescence directed into a root. On the other hand, Wang et al. (J Comb Optim, doi:10.1007/s10878-016-9991-1, 2016) have shown that there exists polynomial-time algorithm for this problem under the linear threshold (LT) model. Hence, this pair of results is of theoretical interest since this is the first time to give a theoretical difference on computational complexity between the IC and LT models. We believe it may motivate further research for influence maximization on arborescence and other special graphs.

Graph-based heuristic for Multiple Constant Multiplication (MCM) has been an area of intensive research over the last two decades. To overcome the pitfalls of hidden partial sums and local minima inherent in trivial digraph formulation, this paper introduces an elementary digraph-to-hypergraph transformation to enable a new minimum arborescence (MA) formulation of MCM problem. Our proposed algorithm iteratively solves the MA problem from a strongly connected graph formed by adding new vertex from the least cost surviving hypergraph in the preceding iteration until no new vertex is found. As the visible and hidden edges of an elementary hypergraph (EHG) are interchangeable by swapping their values encoded in its hyperedge, previously removed vertex can be revived if it is a predecessor of the least cost surviving hyperedge as the hypergraph evolves. A by-product of this iterative algorithm is that its underlying EHG minimization can also be used for quality improvement of existing MCM solutions generated by other design algorithms or for engineering changes. Experimental results on benchmark filters show that our proposed algorithm can reduce their multiplier block areas by 2.9% to 14.9% and power consumptions by 2.8% to 20.1% over other advanced algorithms. A further $\sim$ 20% of area can be saved from the less area-efficient solutions of other design algorithms by the proposed EHG reoptimization.

Bharathi et al. (WINE, pp 306---311, 2007) conjectured that the influence maximization problem is NP-hard for arborescence directed into a root. In this note, we show that this conjecture is not true for deterministic diffusion model and linear threshold (LT) model, that is, there exist polynomial-time algorithms for the influence maximization problem in those two models on arborescence directed into a root. This means that if the conjecture in the independent cascade (IC) model is true, then it would give an interesting difference between the IC model and the LT model.

Nowadays, many political campaigns are using social influence in order to convince voters to support/oppose a specific candidate/party. In election control via social influence problem, an attacker tries to find a set of limited influencers to start disseminating a political message in a social network of voters. A voter will change his opinion when he receives and accepts the message. In constructive case, the goal is to maximize the number of votes/winners of a target candidate/party, while in destructive case, the attacker tries to minimize them. Recent works considered the problem in different models and presented some hardness and approximation results. In this work, we consider multi-winner election control through social influence on different graph structures and diffusion models, and our goal is to maximize/minimize the number of winners in our target party. We show that the problem is hard to approximate when voters&rsquo, connections form a graph, and the diffusion model is the linear threshold model. We also prove the same result considering an arborescence under independent cascade model. Moreover, we present a dynamic programming algorithm for the cases that the voting system is a variation of straight-party voting, and voters form a tree.

We present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS), and node-weighted Steiner tree problem (NWSTP). The main component of our framework is a new dual ascent algorithm for the rooted APCSTP, which generalizes Wong’s dual ascent algorithm for the Steiner arborescence problem. The lower bounds and dual information obtained from the algorithm are exploited within powerful bound-based reduction tests and for guiding primal heuristics. The framework is complemented by additional alternative-based reduction tests. Extensive computational results on benchmark instances for the PCSTP, MWCS, and NWSTP indicate the framework’s effectiveness, as most instances from literature are solved to optimality within seconds, including most of the (previously unsolved) largest instances from the recent DIMACS Challenge on Steiner trees. Moreover, results on new asymmetric instances for the APCSTP are reported. Since the addressed network design problems are frequently used for modeling various real-world applications (e.g., in bioinformatics), the implementation of the presented B&B framework has been made publicly available.

The augmentation problem originally determines a minimum weight arc-set that is added to an original network to satisfy a given property. In the real communication network, continuous transmission may lead some transmission lines of this original network to be damaged such that communication network cannot be used. The problem that we consider is how to add other transmission lines to construct a more survivable communication network to service well. In details, we consider the constrained arborescence augmentation problem (CAA, for short) as follows. For a given weighted digraph (or network) D = (V, A; w;T r ), where w:A → R+, is a weighted function and T r (V, A r ) is an arborescence rooted at r in D, we are asked to find an arc-subset A′ from A-A r such that there exists still an arborescence in the new digraph D′ = (V, A r ∪ A′-{a}) for each arc a ∊ A r , the objective is to minimize the total weight w(A′) = ∑ e∊A′ w(e). In this paper, we prove that the CAA problem still remains NP-hard, whose proof follows from a reduction from the 3-dimensional matching. In addition, we present an optimal combinatorial algorithm in O(m + n log n) time to solve this problem for special version where an arborescence in digraph D′ = (V, A r ∪ A′-{a}) still has its fixed root r, for each arc a ∊ A r .

We consider the Erd\H{o}s-R\'enyi random directed graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let $\mathcal{D}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,\ldots, m$) of $\mathcal{D}(n,m)$ independently chooses a colour, taken uniformly at random from a given set of $n(1 + O( \log \log n / \log n)) = n (1+o(1))$ colours. We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{D}(n,M)$ has at most one vertex that has in-degree zero and there are at least $n-1$ distinct colours introduced ($M= n(n-1)$ if at the time when all edges are present there are still less than $n-1$ colours introduced; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{D}(n,M)$ has a rainbow arborescence (that is, a directed, rooted tree on $n$ vertices in which all edges point away from the root and all the edges are different colours). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is "yes".

In this paper, we consider integral (and fractional) packing problems in generalized kernel systems with a mixed family (gksmf). This framework generalizes combinatorial packing problems of several structures as, for instance, st-flows, arborescences, kernel systems, branchings, convex branchings, and covers in bi-set systems. We provide an algorithm, which improves by a factor of 2 on the upperbound for the size of a packing in a gksmf, provided by Leston-Rey and Wakabayashi. This in turn implies the following upperbounds, where n is the number of vertices, m the number of arcs, and r the number of root-sets of a digraph: m for the size of a packing of st-paths; $$m-n+2$$m-n+2 for the size of a packing of spanning arborescences; $$m+r-1$$m+r-1 for the size of a packing of spanning branchings; $$m+r-1$$m+r-1 for the size of a packing of Fujishige's convex branchings; m for the size of a packing of dijoins of a restricted form; and $$m+r-1$$m+r-1 for the size of a packing in Frank's bi-set systems with the mixed intersection property. Next, we consider the framework of uncrossinggksmf. We describe an algorithm for computing a packing in such a framework with the same upperbound guarantee. The time complexity of this algorithm implies an improvement over the best time complexity bounds known for computing a packing of spanning arborescences of Gabow and Manu, for computing a packing of spanning branchings of Lee and Leston-Rey, and for computing a packing of covers in a bi-set system with the mixed intersection property of Berczi and Frank.

Flow maps visualize the movement of objects between places. One or more sources are connected to several targets by arcs whose thickness corresponds to the amount of flow between a source and a target. Flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding self-intersections. We present algorithms that compute crossing-free flows of high visual quality. To this end we introduce a new variant of the geometric Steiner arborescence problem. The goal is to connect the targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. Such an angle-restricted Steiner arborescence, or simply ow tree, naturally induces a clustering on the targets and smoothly bundles arcs. We study the properties of optimal flow trees and show that they consist of logarithmic spirals and straight lines. Computing optimal flow trees is NP-hard. Hence we consider a variant of flow trees which uses only logarithmic spirals, so called spiral trees. Spiral trees approximate flow trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard. We present an efficient 2-approximation for spiral trees, which can be extended to avoid certain types of obstacles.

To compress large datasets of high-dimensional descriptors, modern quantization schemes learn multiple codebooks and then represent individual descriptors as combinations of codewords. Once the codebooks are learned, these schemes encode descriptors independently. In contrast to that, we present a new coding scheme that arranges dataset descriptors into a set of arborescence graphs, and then encodes non-root descriptors by quantizing their displacements with respect to their parent nodes. By optimizing the structure of arborescences, our coding scheme can decrease the quantization error considerably, while incurring only minimal overhead on the memory footprint and the speed of nearest neighbor search in the compressed dataset compared to the independent quantization. The advantage of the proposed scheme is demonstrated in a series of experiments with datasets of SIFT and deep descriptors.

Complex networks are a useful tool for the understanding of complex systems. One of the emerging properties of such systems is their tendency to form hierarchies: networks can be organized in levels, with nodes in each level exerting control on the ones beneath them. In this paper, we focus on the problem of estimating how hierarchical a directed network is. We propose a structural argument: a network has a strong top-down organization if we need to delete only few edges to reduce it to a perfect hierarchy-an arborescence. In an arborescence, all edges point away from the root and there are no horizontal connections, both characteristics we desire in our idealization of what a perfect hierarchy requires. We test our arborescence score in synthetic and real-world directed networks against the current state of the art in hierarchy detection: agony, flow hierarchy and global reaching centrality. These tests highlight that our arborescence score is intuitive and we can visualize it; it is able to better distinguish between networks with and without a hierarchical structure; it agrees the most with the literature about the hierarchy of well-studied complex systems; and it is not just a score, but it provides an overall scheme of the underlying hierarchy of any directed complex network.

International audience; In this work, we consider the minimum-cost shared Steiner arborescence problem (SStA). In this problem, the goal is to find a minimum-cost subgraph, which is shared among multiple entities and each entity is able to establish a cost-efficient Steiner arborescence. The SStA has been recently used in the literature to establish shared functional modules in protein-protein interaction networks.We propose a cut-based formulation for the problem, and design two exact algorithmic approaches: one based on the separation of connectivity cut inequalities, and the other corresponding to a Benders decomposition of the former model. Both approaches are enhanced by various techniques, including (i) preprocessing, (ii) stabilized cut generation, (iii) primal heuristics, and (iv) cut management. These two algorithmic alternatives are computationally evaluated and compared with a previously proposed flow-based formulation. We illustrate the effectiveness of the algorithms on two types of instances derived from protein-protein interaction networks (available from the previous literature) and from telecommunication access networks.

Given a social network $\mathcal {G}$ and a positive integer $k$ , the influence maximization problem aims to identify a set of $k$ nodes in $\mathcal {G}$ that can maximize the influence spread under a certain propagation model. As the proliferation of geo-social networks, location-aware promotion is becoming more necessary in real applications. In this paper, we study the distance-aware influence maximization (DAIM) problem, which advocates the importance of the distance between users and the promoted location. Unlike the traditional influence maximization problem, DAIM treats users differently based on their distances from the promoted location. In this situation, the $k$ nodes selected are different when the promoted location varies. In order to handle the large number of queries and meet the online requirement, we develop two novel index-based approaches, MIA-DA and RIS-DA, by utilizing the information over some pre-sampled query locations. MIA-DA is a heuristic method which adopts the maximum influence arborescence (MIA) model to approximate the influence calculation. In addition, different pruning strategies as well as a priority-based algorithm are proposed to significantly reduce the searching space. To improve the effectiveness, in RIS-DA, we extend the reverse influence sampling (RIS) model and come up with an unbiased estimator for the DAIM problem. Through carefully analyzing the sample size needed for indexing, RIS-DA is able to return a $1 - 1/e -\epsilon$ approximate solution with at least $1 - \delta$ probability for any given query. Finally, we demonstrate the efficiency and effectiveness of proposed methods over real geo-social networks.

This paper presents a novel algorithm to optimize a topology for tackling the challenge of increasing uncertainty on load demand (growth rate with connection of new loads) in low-voltage (LV) distribution. This paper aims at finding which load connection phase induces the lowest costs (investment and power losses) and phase balancing while satisfying the techno-economic aspects over planning study. A mixed integer quadratically constrained programming (MIQCP) and shortest path-bin packing with arborescence flow are developed to perform this work. To illustrate this method, the example of LV distribution (33 bus) is chosen to be a case study of an initial year. Monte-Carlo (MC) simulation method is employed to evaluate the results. The simulation results obtained on test system support an effectiveness of method.

For a directed graph, a Minimum Weight Arborescence (MWA) rooted at a vertex r is a directed spanning tree rooted at r with the minimum total weight. We define the MinArborescence constraint to solve constrained arborescence problems (CAP) in Constraint Programming (CP). A filtering based on the LP reduced costs requires \(O(|V|^2)\) where |V| is the number of vertices. We propose a procedure to strengthen the quality of the LP reduced costs in some cases, also running in \(O(|V|^2)\). Computational results on a variant of CAP show that the additional filtering provided by the constraint reduces the size of the search tree substantially.

There is an increasing interest in planning sensor networks by considering both the impact of distances among sensors and the risk that power consumption leads to a very small network lifetime. A sensor failure can affect sensors in its neighborhood and compromise the network data communication. Weather conditions may cause the power consumption of data communication to vary with uncertainty. This work introduces a compact probabilistic optimization approach to handle this problem while considering jointly or separately dependence among power consumption of the links of the network in a unified framework. We explore the concept of copulas in a dominating arborescence (DA) model for directed graphs, extended accordingly to handle the uncertain parameters. We give a proof of the DA model correctness and show that it can solve to optimality some benchmark instances of the deterministic dominating tree problem. Numerical results for the probabilistic approach show that our model tackles randomly generated instances with up to 120 nodes.

International audience; We present a new method for the joint task of tagging and non-projective dependency parsing. We demonstrate its usefulness with an application to discontinu-ous phrase-structure parsing where decoding lexicalized spines and syntactic derivations is performed jointly. The main contributions of this paper are (1) a reduction from joint tagging and non-projective dependency parsing to the Generalized Maximum Spanning Arborescence problem, and (2) a novel decoding algorithm for this problem through Lagrangian relaxation. We evaluate this model and obtain state-of-the-art results despite strong independence assumptions.

In this work, we consider the problem of placing replicas in a data center or storage area network, represented as a digraph, so as to lexico-minimize a previously proposed reliability measure which minimizes the impact of all failure events in the model in decreasing order of severity. Prior work focuses on the special case in which the digraph is an arborescence. In this work, we consider the broader class of multitrees: digraphs in which the subgraph induced by vertices reachable from a fixed node forms a tree. We parameterize multitrees by their number of “roots” (nodes with in-degree zero), and rule out membership in the class of fixed-parameter tractable problems (FPT) by showing that finding optimal replica placements in multitrees with 3 roots is NP-hard. On the positive side, we show that the problem of finding optimal replica placements in the class of untangled multitrees is FPT, as parameterized by the replication factor \(\rho \) and the number of roots k. Our approach combines dynamic programming (DP) with a novel tree decomposition to find an optimal placement of \(\rho \) replicas on the leaves of a multitree with n nodes and k roots in \(O(n^2\rho ^{2k+3})\) time.

The classical influence maximization (IM) problem in social networks does not distinguish between whether a campaign gets viral in a week or in a year. From the practical standpoint, however, campaigns for a new technology or an upcoming movie must be spread as quickly as possible, otherwise they will be obsolete. To this end, we formulate and investigate the novel problem of maximizing the time-discounted influence spread in a social network, that is, the campaigner is interested in both "when" and "how likely" a user would be influenced. In particular, we assume that the campaigner has a utility function which monotonically decreases with the time required for a user to get influenced, since the activation of the seed nodes. The problem that we solve in this paper is to maximize the expected aggregated value of this utility function over all network users. This is a novel and relevant problem that, surprisingly, has not been studied before. Time-discounted influence maximization (TDIM), being a generalization of the classical IM, still remains NP-hard. However, our main contribution is to prove the sub-modularity of the objective function for any monotonically decreasing function of time, under a variety of influence cascading models, e.g., the independent cascade, linear threshold, and maximum influence arborescence models, thereby designing approximate algorithms with theoretical performance guarantees. We also illustrate that the existing optimization techniques (e.g., CELF) for influence maximization are more efficient over TDIM. Our experimental results demonstrate the effectiveness of our solutions over several baselines including the classical influence maximization algorithms.

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Changeover Cost Arborescence" (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by G\"oz\"upek et al. [TCS 2016] that the problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for the MINCCA problem: - the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of G\"oz\"upek et al. [TCS 2016]; - it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; - it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in G\"oz\"upek et al. [TCS 2016]; - it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs., Comment: 25 pages, 11 figures

© 2016 IEEE. Influence maximization is a key problem in viral marketing. Given a social network G and a positive integer k, it aims to identify a seed set of k nodes in G that can maximize the expected influence spread in a certain propagation model. With the proliferation of geo-social networks, location-aware product promotion is becoming more necessary in real applications. However, the importance of the distance between users and the promoted location is underestimated in existing models. For instance, when opening a restaurant in downtown, through online promotion, the owner may expect to influence more customers who are close to the restaurant, instead of people that are far away from it. In this paper, we formally define the distance-aware influence maximization problem, to find a seed set that maximizes the expected influence over users who are more likely to be the potential customers of the promoted location. To efficiently calculate the influence spread, we adopt the maximum influence arborescence (MIA) model for influence approximation. To speed up the search, we propose three pruning strategies to prune unpromising nodes from expensive evaluation and achieve potential early termination in each iteration without sacrificing the final result's approximation ratio. In addition, novel index structures are developed to compute the bounds used in the three pruning strategies. By integrating these pruning strategies, we propose a priority based algorithm which searches users based on their order of influence. The algorithm achieves an approximation ratio of 1 - 1 over e under the MIA model. In the final, comprehensive experiments over real datasets demonstrate the efficiency and effectiveness of the proposed algorithms and pruning strategies.

This article comprises the first theoretical and computational study on mixed integer programming (MIP) models for the connected facility location problem (ConFL). ConFL combines facility location and Steiner trees: given a set of customers, a set of potential facility locations and some inter-connection nodes, ConFL searches for the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The costs needed for building the Steiner tree, facility opening costs and the assignment costs need to be minimized.We model ConFL using seven compact and three mixed integer programming formulations of exponential size. We also show how to transform ConFL into the Steiner arborescence problem. A full hierarchy between the models is provided. For two exponential size models we develop a branch-and-cut algorithm. An extensive computational study is based on two benchmark sets of randomly generated instances with up to 1300 nodes and 115,000 edges. We empirically compare the presented models with respect to the quality of obtained bounds and the corresponding running time. We report optimal values for all but 16 instances for which the obtained gaps are below 0.6%.

We present a new approach to large-scale graph mining based on so-called backbone refinement classes. The method efficiently mines tree-shaped subgraph descriptors under minimum frequency and significance constraints, using classes of fragments to reduce feature set size and running times. The classes are defined in terms of fragments sharing a common backbone. The method is able to optimize structural inter-feature entropy as opposed to purely occurrence-based criteria, which is characteristic for open or closed fragment mining. We first give an intuitive explanation why backbone refinement class features lead to a set of relevant features that are suitable for classification, in particular in the area of structure-activity relationships (SARs). We then show that backbone refinement classes yield a high compression in the search space of rooted perfect binary trees. We conduct several experiments to evaluate our theoretical insights in practice: A visualization suggests low co-occurrence and high entropy of backbone refinement class features. By comparison to a class of patterns sampled from the maximal patterns previously introduced by Al Hasan et al., we find a favorable tradeoff between the structural similarity and the resources needed to compute the descriptors. Cross-validation shows that classification accuracy is similar to the complete set of trees but significantly better than that of open trees, while feature set size is reduced by >90% and >30% compared to complete tree mining and open tree mining, respectively. Furthermore, compared to open or closed pattern mining, a large part of the search space can be pruned due to an improved statistical constraint (dynamic upper bound adjustment). This is confirmed experimentally by running times reduced by more than 60% compared to ordinary (static) upper bound pruning. The application of our method to the largest datasets that have been used in correlated graph mining so far indicates robustness against the minimum frequency parameter, and a cross-validation run on this data confirms that the novel descriptors render large training sets feasible, which previously might have been intractable. A C++ implementation of the mining algorithm is available at http://www.maunz.de/libfminer-doc . Animated figures, links to datasets, and further resources are available at http://www.maunz.de/mlj-res .