Search

Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation for this task that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, we apply it to a political districting problem in which contiguity and population balance are imposed as hard constraints and compactness is optimized. Computational experiments show that, despite the model's small size and integrality for connected partitioning, the population balance constraints are more troublesome to effectively impose. Nevertheless, we share our findings in hopes that others may find better ways to impose them. [ABSTRACT FROM AUTHOR]

Every generic linear functional (Formula presented.) on a convex polytope (Formula presented.) induces an orientation on the graph of (Formula presented.). From the resulting directed graph one can define a notion of (Formula presented.) -arborescence and (Formula presented.) -monotone path on (Formula presented.), as well as a natural graph structure on the vertex set of (Formula presented.) -monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of (Formula presented.) -arborescences, the number of (Formula presented.) -monotone paths, and the diameter of the graph of (Formula presented.) -monotone paths for polytopes (Formula presented.) in terms of their dimension and number of vertices or facets.

We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses O ˜ (n 1 / 4) rounds of communication and O ˜ (n 9 / 4) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by O ˜ notation, revealing that advances are needed to render both the quantum and classical algorithms practical. [ABSTRACT FROM AUTHOR]

The everyday expressions of nursing practices are driven by their entanglement in complex flows of social, cultural, political and economic interests. Early expressions of trained nursing practice in the United States and Europe reflect claims of moral, spiritual and clinical exceptionalism. They were both imposed upon-and internalized by-nursing pioneers. These claims were associated with an endogenous narrative of discipline and its physical manifestation in early nursing schools and hospitals, which functioned as "total institutions." By contrast, the external forces-diffuse yet pervasive-impacting upon contemporary nursing more closely align with the power dynamics explored in Gilles Deleuze's concept of the Society of Control. The example of sensor technology and telemetric monitoring of nurses' locations in the clinical setting exemplifies the intense presence of surveillance, performance metrics and the "rationalization" of nursing practice. It falls upon nurses to recognize, accept or challenge these dynamics in order to shape the future of nursing practice into a discipline which embodies our values and priorities.

We introduce a new class of inverse optimization problems in which an input solution is given together with k linear weight functions, and the goal is to modify the weights by the same deviation vector p so that the input solution becomes optimal with respect to each of them, while minimizing ‖ p ‖ 1. In particular, we concentrate on three problems with multiple weight functions: the inverse shortest s − t path, the inverse bipartite perfect matching, and the inverse arborescence problems. Using LP duality, we give min–max characterizations for the ℓ 1 -norm of an optimal deviation vector. Furthermore, we show that the optimal p is not necessarily integral even when the weight functions are so, therefore computing an optimal solution is significantly more difficult than for the single-weighted case. We also give a necessary and sufficient condition for the existence of an optimal deviation vector that changes the values only on the elements of the input solution, thus giving a unified understanding of previous results on arborescences and matchings. [ABSTRACT FROM AUTHOR]

In the directed minimum spanning tree problem (DMST, also called minimum weight arborescence), we are given a directed weighted graph, and a root node r. Our goal is to construct a minimum-weight directed spanning tree, rooted at r and oriented outwards. We present the first sub-quadratic DMST algorithm in the distributed CONGEST network model, where the messages exchanged between the network nodes are bounded in size. We consider three versions of the model: a network where the communication links are bidirectional but can have different weights in the two directions; a network where communication is unidirectional; and the Congested Clique model, where all nodes can communicate directly with each other. Our DMST algorithm is based on a variant of Lovász' DMST algorithm for the PRAM model, and uses a distributed single-source shortest-path (SSSP) algorithm for directed graphs as a black box. In the bidirectional CONGEST model, our algorithm has roughly the same running time as the SSSP algorithm that is used as a black box; using the state-of-the-art SSSP algorithm due to Chechik and Mukhtar (in: Symposium on principles of distributed computing (PODC), ACM, 2020, pp 464–473), we obtain a running time of O ~ (n D 1 / 4 + D)) rounds for the bidirectional communication case. For the unidirectional communication model we give an O ~ (n) algorithm, and show that it is nearly optimal. And finally, for the Congested Clique, our algorithm again matches the best known SSSP algorithm: it runs in O ~ (n 1 / 3) rounds. On the negative side, we adapt an observation of Chechik in the sequential setting to show that in all three models, the DMST problem is at least as hard as the (s, t)-shortest path problem. Thus, in terms of round complexity, distributed DMST lies between single-source shortest path and (s, t)-shortest path. [ABSTRACT FROM AUTHOR]

Given a digraph with arc costs and a prescribed root vertex r, one asks to find a cheapest spanning r-arborescence, i.e., a spanning out-tree growing from r with the least total cost. There are known several algorithms for this problem which are very similar. The essence of those algorithms is usually called as Edmonds' algorithm. We slightly generalize the algorithm and give an easy proof. Further, we study variations of the problem where a restriction on out-degrees is considered and show that they are NP-hard and inapproximable even for simplified digraphs. [ABSTRACT FROM AUTHOR]

Fortier et al. proposed several research problems on packing arborescences and settled some of them. Others were later solved by Matsuoka and Tanigawa and by Gao and Yang. The last open problem is settled in this article. We show how to turn an inductive idea used in the latter two articles into a simple proof technique that allows to relate previous results on arborescence packings. We prove that a strong version of Edmonds' theorem on packing spanning arborescences implies Kamiyama, Katoh and Takizawa's result on packing reachability arborescences and that Durand de Gevigney, Nguyen and Szigeti's theorem on matroid-based packing of arborescences implies Király's result on matroid-reachability-based packing of arborescences. Further, we deduce a new result on matroid-reachability-based packing of mixed hyperarborescences from a theorem on matroid-based packing of mixed hyperarborescences due to Fortier et al.. Finally, we deal with the algorithmic aspects of the problems considered. We first obtain algorithms to find the desired packings of arborescences in all settings and then apply Edmonds' weighted matroid intersection algorithm to also find solutions minimizing a given weight function. [ABSTRACT FROM AUTHOR]

We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses O˜(n1/4) rounds of communication and O˜(n9/4) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by O˜ notation, revealing that advances are needed to render both the quantum and classical algorithms practical.

Given a connected digraph, a vertex designated as the root, and an integer p$p$, the p$p$‐arborescence star problem is to choose p$p$ vertices besides the root and define a reverse arborescence spanning them. Each vertex outside the arborescence must be assigned to one vertex inside it. The objective of the problem is to minimize arborescence and assignment costs. We propose two formulations for the problem and prove theoretical results about their strength. Moreover, we develop branch‐and‐cut algorithms based on each one of the formulations and improve an earlier branch‐and‐cut algorithm for the problem with an exact separation method. Additionally, we show that finding a feasible solution for an arbitrary instance is NP‐hard and introduce preprocessing procedures for the problem. The proposed algorithms are evaluated with a set of benchmark instances from the literature. For small and medium‐sized instances, our proposed algorithms provide the best results when compared to the existing algorithm from the literature. For large instances, the proposed algorithms are shown to be competitive with the existing approach. [ABSTRACT FROM AUTHOR]

Threat models and attack graphs have been used more than 20 years by enterprises and organizations for mapping the actions of potential adversaries, analyzing the effects of vulnerabilities and visualizing attack scenarios. Although efficient when describing high-level interactions in simpler enterprise networks, they fall short in modern decentralized systems, especially in microservices architectures and multi-cloud environments with increased complexity and interactions. Most current research focuses on automatically generating attach graphs for such complex environments and deals with scaling and mapping issues, while neglecting to address the overall complexity of actually analyzing and extracting useful information from these overly convoluted models. In this paper, we present a method for automatically analyzing complex attack graphs both in microservices-based and multi-cloud infrastructures. We piggyback on previous research to automatically create complex attack graphs for such enterprise networks and use it as input to relate microservices, virtual system states and cloud services (represented as graph nodes) with prioritization algorithms that use mathematical graph series and group clustering. Our tool prioritizes existing vulnerabilities, analyzes the effect of system states to the overall network and proposes which system states, vulnerabilities and configurations have the biggest overall risk to the ecosystem, while taking into consideration every potential sub-attack path and subliminal path on an attack graph. We test the efficiency of our software on two real-world use cases: one multi-cloud enterprise network and a NetFlixOSS microservices Docker architecture. [ABSTRACT FROM AUTHOR]

Gordon and McMahon defined a two-variable greedoid polynomial f(G; t, z) for any greedoid G. They studied greedoid polynomials for greedoids associated with rooted graphs and rooted digraphs. They proved that greedoid polynomials of rooted digraphs have the multiplicative direct sum property. In addition, these polynomials are divisible by 1 + z under certain conditions. We compute the greedoid polynomials for all rooted digraphs up to order six. A polynomial is said to factorise if it has a non-constant factor of lower degree. We study the factorability of greedoid polynomials of rooted digraphs, particularly those that are not divisible by 1 + z . We give some examples and an infinite family of rooted digraphs that are not direct sums but their greedoid polynomials factorise. [ABSTRACT FROM AUTHOR]

In this paper, we characterize a mixed graph F which contains k edge and arc‐disjoint spanning mixed arborescences F1,...,Fk, such that for each v∈V(F), the cardinality of {i∈[k]:vis the root ofFi} lies in some prescribed interval. This generalizes both Nash‐Williams and Tutte's theorem on spanning tree packing for undirected graphs and the previous characterization on digraphs which was given by Cai and Frank. [ABSTRACT FROM AUTHOR]

In 1998, Hu and Liu developed a strongly polynomial algorithm for solving the inverse arborescence problem that aims at minimally modifying a given cost-function on the edge-set of a digraph D so that an input spanning arborescence of D becomes a cheapest one. In this note, we develop a conceptually simpler algorithm along with a new min–max formula for the minimum modification of the cost-function. The approach is based on a link to a min–max theorem and a simple (two-phase greedy) algorithm by the first author from 1979 concerning the primal optimization problem of finding a cheapest subgraph of a digraph that covers an intersecting family along with the corresponding dual optimization problem, as well. [ABSTRACT FROM AUTHOR]

This paper studies the following packing problem: Given a mixed graph F with vertex set V , a matroid M on a set S = { s 1 , ... , s k } along with a map π : S → V , find k mutually edge and arc-disjoint mixed arborescences T 1 , ... , T k in F with roots π (s 1) , ... , π (s k) , such that, for any v ∈ V , the set { s i : v ∈ V (T i) } is independent and its rank reaches the theoretical maximum. This problem was mentioned by Fortier, Király, Léonard, Szigeti and Talon in [Old and new results on packing arborescences in directed hypergraphs, Discrete Appl. Math. 242 (2018), 26-33]; Matsuoka and Tanigawa gave a solution to this in [On reachability mixed arborescence packing, Discrete Optimization 32 (2019) 1-10]. In this paper, we give a new characterization for above packing problem. This new characterization is simplified to the form of finding a supermodular function that should be covered by an orientation of each strong component of a matroid-based rooted mixed graph. Our proofs come along with a polynomial-time algorithm. The technique of using components opens some new ways to explore arborescence packings. [ABSTRACT FROM AUTHOR]

The separate delivery and collection services of goods through different routes is an issue of current interest for some transportation companies by the need to avoid the reorganization of the loads inside the vehicles, to reduce the return of the vehicles with empty load and to give greater priority to the delivery customers. In the vehicle routing problem with backhauls (VRPB), the customers are partitioned into two subsets: linehaul (delivery) and backhaul (pickup) customers. Additionally, a precedence constraint is established: the backhaul customers in a route should be visited after all the linehaul customers. The VRPB is presented in the literature as an extension of the capacitated vehicle routing problem and is NP-hard in the strong sense. In this paper, we propose a mixed integer linear programming formulation for the VRPB, based on the generalization of the open vehicle routing problem; that eliminates the possibility of generating solutions formed by subtours using a set of new constraints focused on obtaining valid solutions formed by Hamiltonian paths and connected by tie-arcs. The proposed formulation is a general purpose model in the sense that it does not deserve specifically tailored algorithmic approaches for their effective solution. The computational results show that the proposed compact formulation is competitive against state-of-the-art exact methods for VRPB instances from the literature.

In this paper, we introduce the concept of b -branchings in digraphs, which is a generalization of branchings serving as a counterpart of b -matchings. Here b is a positive integer vector on the vertex set of a digraph D , and a b -branching is defined as a common independent set of two matroids defined by b : an arc set is a b -branching if it has, for every vertex v of D , at most b (v) arcs entering v , and it is an independent set of a certain sparsity matroid defined by b and D. We demonstrate that b -branchings yield an appropriate generalization of branchings by extending several classic results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b -branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b -branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b -branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b (v) arcs sharing the terminal vertex v. [ABSTRACT FROM AUTHOR]

We study the problem of packing arborescences in the random digraph D (n, p), where each possible arc is included uniformly at random with probability p = p(n). Let λD(n,p) denote the largest integer λ ≥ 0 such that, for all 0 ≤ l ≤ λ, we have Σl-1i=0(l-i)|{:din(v)=i}| ≤ l . We show that the maximum number of arc-disjoint arborescences in D(n, p) is λ (D(n, p)) asymptotically almost surely. We also give tight estimates for λ (D(n, p)) depending on the range of p. [ABSTRACT FROM AUTHOR]

The aim of this paper is twofold. We first provide a new orientation theorem which gives a natural and simple proof of a result of Gao and Yang (2021) on matroid-reachability-based packing of mixed arborescences in mixed graphs by reducing it to the corresponding theorem of Király (2016) on directed graphs. Moreover, we extend another result of Gao and Yang (2021) by providing a new theorem on mixed hypergraphs having a packing of mixed hyperarborescences such that their number is at least ℓ and at most ℓ ′ , each vertex belongs to exactly k of them, and each vertex v is the root of least f (v) and at most g (v) of them. [ABSTRACT FROM AUTHOR]

This paper suggests that the imbrication of user-friendly software and the posthuman has increasingly been revealed as an intrinsically arborescent relationship, one premised upon the striation of personal information through different forms of software media and allowing for unprecedented avenues of control and subjective manipulation. My analysis begins with a conceptualisation of user-friendliness, tracing its development as the majoritarian style of software design. In assessing the effects of this process of subjective imbrication with arborescent software technology, it is suggested that one effect of the pathological asignification of instrumentality in the representation of software is the genesis of a topological space which allows for a capacity for control over the subjective becoming of others through control over digitally mediated perception. To illustrate this point, the revelations concerning Cambridge Analytica's use of targeted advertisements on Facebook to affect voting preferences during the 2016 American presidential election are examined as an example of the quotidian domination which is characteristic of the subjective condition of arbormosis. This analysis can be applied to issues of gender, technology, and modes of subjective control. [ABSTRACT FROM AUTHOR]

We propose a further development in the theory of packing arborescences. First we review some of the existing results on packing arborescences and then we provide common generalizations of them to directed hypergraphs. We introduce and solve the problem of reachability-based packing of matroid-rooted hyperarborescences and we also solve the minimum cost version of this problem. Furthermore, we introduce and solve the problem of matroid-based packing of matroid-rooted mixed hyperarborescences. [ABSTRACT FROM AUTHOR]

ContentsI.II.III.IV.V.AcknowledgementsReferences Summary: Flowering plants can be far more productive than other living land plants. Evidence is reviewed that productivity would have been uniformly lower and less CO2‐responsive before angiosperm evolution, particularly during the early evolution of vascular plants and forests in the Devonian and Carboniferous. This introduces important challenges because paleoecological interpretations have been rooted in understanding of modern angiosperm‐dominated ecosystems. One key example is tree evolution: although often thought to reflect competition for light, light limitation is unlikely for plants with such low photosynthetic potential. Instead, during this early evolution, the capacities of trees for enhanced propagule dispersal, greater leaf area, and deep‐rooting access to nutrients and the water table are all deemed more fundamental potential drivers than light. See also the Commentary on this article by Friedman, 215: 505–507. [ABSTRACT FROM AUTHOR]

By generalizing the results of [N. Kamiyama, N. Katoh, and A. Takizawa, Combi-natorica, 29 (2009), pp. 197-214], we solve the following problem. Given a digraph D = (V,A) and a matroid on a set S = {s1. . . . , sk} along with a map π : S → V, find κ edge-disjoint arborescences T1, . . . , Tκ with roots π(s1), . . . , π(sk), respectively, such that, for any ν ∊ V, the set {si : ν ∊ Ti} is independent and its rank reaches the theoretical maximum. We also give a simplified proof for a result of [S. Fujishige, Combinatorica, 30 (2010), pp. 247-252]. [ABSTRACT FROM AUTHOR]

Let D be a finite digraph, and let [ABSTRACT FROM AUTHOR]

We consider the Erdős-Rényi 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 [ABSTRACT FROM AUTHOR]

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$$ for the size of a packing of spanning arborescences; $$m+r-1$$ for the size of a packing of spanning branchings; $$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$$ for the size of a packing in Frank's bi-set systems with the mixed intersection property. Next, we consider the framework of uncrossing gksmf. 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 Bérczi and Frank. [ABSTRACT FROM AUTHOR]