Resilient Broadcasting via Independent Spanning-Trees

衡量通信网络弹性的一个经典理论指标是其边缘连通性。然而，对于某些网络问题，这种措施根本不适合。例如，在弹性广播中，一个指定的顶点r通过一组生成树与所有其他顶点通信，对于每个顶点v，这些生成树中从r到v的路径是边不相交的（这样的树被称为独立的）。但是，一个网络中独立生成树的最大数量究竟与它的边连通性有多大关系，这是未知的，关于顶点故障的类似问题或寻找这种独立生成树的复杂性，也没有更多的了解。事实上，图论中存在已久的边无关生成树猜想认为，每个k边连通网络包含k棵独立生成树。这一猜想的证明不仅可以表征弹性广播可能存在的网络，而且还可以提供对此类网络的紧凑设计和这些网络中的有效路由方案所必需的结构见解。虽然最近在小k的这个猜想上有结构和算法上的进展（在这种情况下，猜想是正确的），但到目前为止还没有实现对更高k的推广。该项目旨在使用最近提出的结构来攻击更高k的边缘无关生成树猜想。我们将使用图论方法来搜索更高k的正确泛化，但也使用计算机辅助算法来支持这种搜索。

A classic theoretical measure for the resilience of a communication network is its edge-connectivity. However, for some network problems, this measure is not known to be suitable at all. In resilient broadcasting, for example, one prescribed vertex r communicates with every other vertex through a set of spanning trees such that, for every vertex v, the paths from r to v in these spanning trees are edge-disjoint (such trees are called independent). But it is unknown how exactly the maximal number of independent spanning trees in a network relate to its edge-connectivity, and nothing more is known for the analogous question regarding vertex-failures or for the complexity of finding such independent spanning trees.In fact, the long-standing Edge-Independent Spanning Tree Conjecture in graph theory states that every k-edge-connected network contains k independent spanning trees. A proof of this conjecture would not only characterize the networks in which resilient broadcasting is possible, but arguably also deliver the structural insights that are necessary for the compact design of such networks and for efficient routing schemes in these. Although there is recent structural and algorithmic progress on this conjecture for small k (in which case the conjecture is true), a generalization to higher k was not achieved so far.This project aims at attacking the Edge-Independent Spanning Tree Conjecture for higher k, using the recently proposed structures. We will use graph-theoretic methods in order to search for the right generalization to higher k but also computer-assisted algorithms to support this search.