Search

In 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call (tw , ω) -bounded. The family of (tw , ω) -bounded graph classes provides a unifying framework for a variety of very different families of graph classes, including graph classes of bounded treewidth, graph classes of bounded independence number, intersection graphs of connected subgraphs of graphs with bounded treewidth, and graphs in which all minimal separators are of bounded size. While Chaplick and Zeman showed in 2017 that (tw , ω) -bounded graph classes enjoy some good algorithmic properties related to clique and coloring problems, it is an interesting open problem to which extent (tw , ω) -boundedness has useful algorithmic implications for problems related to independent sets. We provide a partial answer to this question by identifying a sufficient condition for (tw , ω) -bounded graph classes to admit a polynomial-time algorithm for the Maximum Weight Independent Packing problem and, as a consequence, for the weighted variants of the Independent Set and Induced Matching problems. Our approach is based on a new min-max graph parameter related to tree decompositions. We define the independence number of a tree decomposition T of a graph as the maximum independence number over all subgraphs of G induced by some bag of T. The tree-independence number of a graph G is then defined as the minimum independence number over all tree decompositions of G. Boundedness of the tree-independence number is a refinement of (tw , ω) -boundedness that is still general enough to hold for all the aforementioned families of graph classes. Generalizing a result on chordal graphs due to Cameron and Hell from 2006, we show that if a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Packing problem can be solved in polynomial time. Applications of our general algorithmic result to specific graph classes are given in the third paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure]. [ABSTRACT FROM AUTHOR]

An out-branching B u + (in-branching B u −) in a digraph D is a connected spanning subdigraph of D in which every vertex except the vertex u , called the root, has in-degree (out-degree) one. A good (u,v) - pair in D is a pair of branchings B u + , B v − which have no arc in common. Thomassen proved that it is NP-complete to decide if a digraph has any good pair. A digraph is semicomplete if it has no pair of non-adjacent vertices. A semicomplete composition is any digraph D which is obtained from a semicomplete digraph S by substituting an arbitrary digraph H x for each vertex x of S. Recently the authors of this paper gave a complete classification of semicomplete digraphs which have a good (u , v) -pair, where u , v are prescribed vertices. They also gave a polynomial algorithm which for a given semicomplete digraph D and vertices u , v of D , either produces a good (u , v) -pair in D or a certificate that D has no such pair. In this paper we show how to use the result for semicomplete digraphs to completely solve the problem of characterizing semicomplete compositions which have a good (u , v) -pair for given vertices u , v. Our solution implies that the problem of deciding the existence of a good (u , v) -pair and finding such a pair when it exists is polynomially solvable for all semicomplete compositions. We also completely solve the problem of deciding the existence of a good (u , v) -pair and finding one when it exists for digraphs that are compositions of transitive digraphs. Combining these two results we obtain a polynomial algorithm for deciding whether a given quasi-transitive digraph D has a good (u , v) -pair for given vertices u , v of D. This proves a conjecture of Bang-Jensen and Gutin from 1998. [ABSTRACT FROM AUTHOR]

Trees with many leaves have applications for broadcasting a message to all recipients simultaneously. Internal nodes of a broadcasting tree require more expensive technology to forward the messages received. We address a problem that captures the main goal: finding spanning trees with few internal nodes in a given network. The Maximum Leaf Spanning Arborescence problem consists of, given a directed graph D , finding a spanning arborescence of D , if one exists, with the maximum number of leaves. This problem is NP-hard in general and MaxSNP-hard in the rooted directed acyclic graphs class. This paper explores a relationship between Maximum Leaf Spanning Arborescence in rooted directed acyclic graphs and maximum weight set packing. The latter problem is related to independent sets on particular classes of intersection graphs. Exploiting this relation, we derive a 7/5-approximation for Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs, improving on the previous 3/2-approximation. [ABSTRACT FROM AUTHOR]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. (2019) [18] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks B n and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O (n ⋅ n !) of our algorithm is asymptotically optimal, where n is the dimension of B n and n ! is the number of vertices of the network. • We present an algorithm for constructing multiple independent spanning trees in bubble-sort networks. • Our approach can be fully parallelized, thus solving an open problem from Kao et al. (2019). • We show that the total time complexity of our algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

Let T G (x , y) be the Tutte polynomial of a graph G. In this paper we show that if (G n) n is a sequence of d -regular graphs with girth g (G n) → ∞ , then for x ≥ 1 and 0 ≤ y ≤ 1 we have lim n → ∞ ⁡ T G n (x , y) 1 / v (G n) = t d (x , y) , where t d (x , y) = { (d − 1) ( (d − 1) 2 (d − 1) 2 − x) d / 2 − 1 if x ≤ d − 1 and 0 ≤ y ≤ 1 , x (1 + 1 x − 1) d / 2 − 1 if x > d − 1 and 0 ≤ y ≤ 1. If (G n) n is a sequence of random d -regular graphs, then the same statement holds true asymptotically almost surely. This theorem generalizes results of McKay (x = 1 , y = 1 , spanning trees of random d -regular graphs) and Lyons (x = 1 , y = 1 , spanning trees of large-girth d -regular graphs). Interesting special cases are T G (2 , 1) counting the number of spanning forests, and T G (2 , 0) counting the number of acyclic orientations. [ABSTRACT FROM AUTHOR]

Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the Hamming distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., cycle-freeness, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs do not. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O (log ⁡ n) bits, and on O (log 2 ⁡ n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers. • A new notion of distributed certification is defined, that ensures better fault-tolerance. • A structural characterization of the problems that admit such certification is proved. • Compact such certification are described and proved. [ABSTRACT FROM AUTHOR]

The characterization of rigid graphs in R d for d ≥ 3 is a major open problem in rigidity theory. The same holds for globally rigid graphs. In this paper our goal is to give necessary and/or sufficient conditions for the (global) rigidity of the square G 2 (and more generally, the power G k) of a graph G in R d , for some values of k , d. Our work is motivated by some results and conjectures of M. Cheung and W. Whiteley from 2008, the Molecular Theorem of N. Katoh and S. Tanigawa from 2011, which settled the case of rigidity for k = 2 , d = 3 , and the potential applications in molecular conformation and sensor network localization. We first consider the case when k = d and characterize those graphs G for which G d is globally rigid in R d , for all d ≥ 1 , and then focus on the case when k = d − 1. We provide a new, direct proof for the 3-dimensional bar-and-joint version of the Molecular Theorem (d = 3) and a necessary condition for the rigidity of G d − 1 in R d , for all d ≥ 3. We conjecture that this condition is also sufficient. The global rigidity of square graphs in R 3 is still an open problem. We formulate a Molecular Global Rigidity Conjecture, which proposes a combinatorial characterization of globally rigid square graphs in terms of vertex partitions and edge count conditions. We prove that the condition is necessary. For the general case we give a best possible connectivity based sufficient condition by showing that if G is 3-edge-connected then G d − 1 is globally rigid in R d , for all d ≥ 3. Our results imply affirmative answers to the conjectures of M. Cheung and W. Whiteley in two special cases. [ABSTRACT FROM AUTHOR]

We study the multicolour discrepancy of spanning trees and Hamilton cycles in graphs. As our main result, we show that under very mild conditions, the r -colour spanning-tree discrepancy of a graph G is equal, up to a constant, to the minimum s such that G can be separated into r equal parts by deleting s vertices. This result arguably resolves the question of estimating the spanning-tree discrepancy in essentially all graphs of interest. In particular, it allows us to immediately deduce as corollaries most of the results that appear in a recent paper of Balogh, Csaba, Jing and Pluhár, proving them in wider generality and for any number of colours. We also obtain several new results, such as determining the spanning-tree discrepancy of the hypercube. For the special case of graphs possessing certain expansion properties, we obtain exact asymptotic bounds. We also study the multicolour discrepancy of Hamilton cycles in graphs of large minimum degree, showing that in any r -colouring of the edges of a graph with n vertices and minimum degree at least r + 1 2 r n + d , there must exist a Hamilton cycle with at least n r + 2 d edges in some colour. This extends a result of Balogh et al., who established the case r = 2. The constant r + 1 2 r in this result is optimal; it cannot be replaced by any smaller constant. [ABSTRACT FROM AUTHOR]

In this paper, we survey some properties, encoding, and bijections involving combinatorial maps, double occurrence words, and chord diagrams. We particularly study quasi-trees from a purely combinatorial point of view and derive a topological representation of maps with a given spanning quasi-tree using two fundamental polygons, which extends the representation of planar maps based on the equivalence with bipartite circle graphs. Then, we focus on Depth-First Search trees and their connection with a poset we define on the spanning quasi-trees of a map. We apply the bijections obtained in the first section to the problem of enumerating loopless rooted maps. Finally, we return to the planar case and discuss a decomposition of planar rooted loopless maps and its consequences on planar rooted loopless map enumeration. [ABSTRACT FROM AUTHOR]

This paper revisits the notion of a spanning hypertree of a hypermap introduced by one of its authors and shows that it allows to shed new light on a very diverse set of recent results. The tour of a map along one of its spanning trees used by Bernardi may be generalized to hypermaps and we show that it is equivalent to a dual tour described by Cori (1976) and Machì(1982). We give a bijection between the spanning hypertrees of the reciprocal of the plane graph with 2 vertices and n parallel edges and the meanders of order n and a bijection of the same kind between semimeanders of order n and spanning hypertrees of the reciprocal of a plane graph with a single vertex and n / 2 nested edges. We introduce hyperdeletions and hypercontractions in a hypermap which allow to count the spanning hypertrees of a hypermap recursively, and create a link with the computation of the Tutte polynomial of a graph. Having a particular interest in hypermaps which are reciprocals of maps, we generalize the reduction map introduced by Franz and Earnshaw to enumerate meanders to a reduction map that allows the enumeration of the spanning hypertrees of such hypermaps. [ABSTRACT FROM AUTHOR]

In this paper, we provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs in two different ways: (1) We represent spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper-Hafnians (orders and signs are not considered); (2) We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam (2004) [1] and Pfaffian matrix tree theorem by Masbaum and Vaintrob (2002) [15]. • We provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper- Hafnians when orders and signs are not considered. • We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam [Advances in Applied Mathematics (2004) Vol. 33: 51-70] and Pfaffian matrix tree theorem by Masbaum and Vaintrob [Internat. Math. Res. Notices (2002) Vol. 27: 1397-1426]. [ABSTRACT FROM AUTHOR]

A graph transformation called the compression of a graph G is known to decrease the number of spanning trees, the all-terminal reliability, and the magnitude of the coefficients of the chromatic polynomial of a graph G. All of these graph parameters can be derived from the Tutte polynomial of G , and in this paper we determine more generally compression's effect on the Tutte polynomial, recovering the previous results and obtaining similar results for a wide variety of other graph parameters derived from the Tutte polynomial. Since any simple connected graph can be transformed into a connected threshold graph via a series of compressions, this gives that threshold graphs are extremal simple graphs for all of the parameters considered. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. • LHABcast is a fully decentralized leaderless algorithm broadcast algorithm. • LHABcast organizes processes on a vCube, which has several logarithmic properties. • LHABcast uses autonomic spanning trees rooted at the sender for message dissemination. • LHABcast is described with examples, and multiple properties are proved. • LHABcast was evaluated both with a Neko simulation and using the Java Akka framework. [ABSTRACT FROM AUTHOR]

Existing stereo matching algorithms suffer from issues such as susceptibility to distortion, weak noise resistance, and a high rate of mismatches in regions with weak textures and discontinuous disparities. To address these challenges, this paper proposes a stereo matching algorithm based on an improved census transform and minimum spanning tree (MST) cost aggregation. In the cost calculation phase, we employ a Gaussian-weighted transformation window and incorporate gradient and edge information to perform weighted fusion of the results. In the cost aggregation process, we introduce a collaborative adaptive window. Each pixel acquires information from the support window of the guided filter (GF) and other pixels within the MST. Furthermore, we integrate the SLIC superpixel segmentation algorithm into MST construction. These two components work synergistically to assign appropriate adaptive weights to pixels, facilitating coordinated cost volume aggregation. Different optimization methods are applied to address mismatched points of various types in post-disparity processing.Performance evaluation using the Middlebury dataset and KITTI dataset demonstrates that our proposed algorithm not only enhances matching accuracy in regions with discontinuous disparities and weak textures but also exhibits significantly improved robustness to interference. Additionally, the resulting disparity map displays smoother edges. • Cost Calculation Phase: Introducing a Gaussian-weighted transformation window, along with gradient and edge information, enables weighted fusion of results. • Cost Aggregation Process: Collaborative adaptive window introduction allows each pixel to gather information from the support window of the guided filter and neighboring pixels within the Minimum Spanning Tree(MST).Furthermore,the SLIC superpixel segmentation algorithm is integrated into the construction of the MST. • Post-Disparity Processing Optimization: Applying diverse optimization methods addresses mismatches among different types of points. [ABSTRACT FROM AUTHOR]

By using biclique partitions of digraphs, this paper gives reduction formulas for the number of oriented spanning trees, stationary distribution vector and Kemeny's constant of digraphs. As applications, we give a method for enumerating spanning trees of undirected graphs by vertex degrees and biclique partitions. The biclique partition formula also extends the results of Knuth and Levine from line digraphs to general digraphs. [ABSTRACT FROM AUTHOR]

This paper describes a floating-frame-of-reference-based (FFRF-based) recursive formulation for flexible bodies. A new definition of the joint coordinate system is introduced that makes it simpler to formulate more concise velocity transformation matrices. A path matrix, which defines the connectivity of the mechanism for the open loop system, simplifies introducing the topology of the rigid and/or flexible spanning tree. The flexible multibody system is often subjected to large reference motion but small deformations. Both Euler–Bernoulli-based beam (EBB) and continuum-mechanics-based beam (CMB) elements are implemented to validate the proposed approach. The reference conditions mentioned here are used to eliminate the rigid body motion from the deformation field, i.e., removal of the coordinate redundancy, in the FFRF. Thus, different reference conditions, such as simply supported, single-cantilever, and double-cantilever are used. Finally, it is demonstrated that the proposed approach is not limited by the choice of reference conditions, which helps the modeler to apply the approach to different multibody applications. In the numerical analysis, the results of the total energy variation and constraint violations of the close loop systems are fulfilled with good accuracy by using both penalty formulation with augmented Lagrangian method and coordinate partitioning approach for constraint stabilization. Furthermore, the proposed semi-recursive method produces dynamic analysis results comparable to the ANCF with better computational efficiency. In the end, compared to fully recursive approach, the proposed semi-recursive approach shows better efficiency and easier implementation. [ABSTRACT FROM AUTHOR]

We give a new proof of the Skeletal Lemma, which is the main technical tool in our paper on Hamilton cycles in line graphs (Kaiser and Vrána, 2012). It generalises results on disjoint spanning trees in graphs to the context of 3-hypergraphs. The lemma is proved in a slightly stronger version that is more suitable for applications. The proof is simplified and formulated in a more accessible way. [ABSTRACT FROM AUTHOR]

Let α ′ and μ i denote the matching number of a non-empty simple graph G with n vertices and the i th smallest eigenvalue of its Laplacian matrix, respectively. In this paper, we prove a tight lower bound α ′ ≥ min ⌈ μ 2 μ n (n − 1) ⌉ , ⌈ 1 2 (n − 1) ⌉ . This bound strengthens the result of Brouwer and Haemers who proved that if n is even and 2 μ 2 ≥ μ n , then G has a perfect matching. A graph G is factor-critical if for every vertex v ∈ V (G) , G − v has a perfect matching. We also prove an analogue to the result of Brouwer and Haemers mentioned above by showing that if n is odd and 2 μ 2 ≥ μ n , then G is factor-critical. We use the separation inequality of Haemers to get a useful lemma, which is the key idea in the proofs. This lemma is of its own interest and has other applications. In particular, we prove similar results for the number of balloons, spanning even subgraphs, as well as spanning trees with bounded degree. [ABSTRACT FROM AUTHOR]