A New Connection Between Node and Edge Depth Robust Graphs
share
We create a graph reduction that transforms an (e, d)-edge-depth-robust graph with m edges into a (e/4,d)-depth-robust graph with O(m) nodes and constant indegree. An (e,d)-depth robust graph is a directed, acyclic graph with the property that that after removing any e nodes of the graph there remains a path with length at least d. Similarly, an (e, d)-edge-depth robust graph is a directed, acyclic graph with the property that after removing any e edges of the graph there remains a path with length at least d. Our reduction relies on constructing graphs with a property we define and analyze called ST-Robustness. We say that a directed, acyclic graph with n inputs and n outputs is (k_1, k_2)-ST-Robust if we can remove any k_1 nodes and there exists a subgraph containing at least k_2 inputs and k_2 outputs such that each of the k_2 inputs is connected to all of the k_2 outputs. We use our reduction on a well known edge-depth-robust graph to construct an (n loglog n/log n, n/log n (log n)^loglog n)-depth-robust graph.
READ FULL TEXT