IEEE INFOCOM is a top-ranked conference on networking in the research community. It is a major conference venue for researchers to present and exchange significant and innovative contributions and ideas in the field of networking and closely related areas. IEEE INFOCOM covers both theoretical and systems research. For INFOCOM 2022, the acceptance ratio is 19.9%. Our below submission was selected to present on the conference. Congratulations to all authors!

Title: Optimal Shielding to Guarantee Region-Based Connectivity under Geographical Failures

Authors: Binglin Tao, Mingyu Xiao, Bakhadyr Khoussainov, Junqiang Peng

In this paper, we consider region-based connectivity to capture the local nature of failures under the geographical failure model, where failures may happen only on edges in a sub-network (region) and we want to shield some edges in regions to protect the connectivity. Firstly, we establish the NP-hardness of the problem for multiple regions, answering a question proposed in previous papers. Secondly, we propose a polynomial-time algorithm for the special case of two regions based on the matroid techniques. Furthermore, we design an ILP-based algorithm to solve the problem for multiple regions. The reviewers of this paper said that: The problem is interesting, and the paper has many theoretical contributions. The new algorithms are built on advanced combinatorial tools which can be also evaluated on various network topologies. The detailed complexity study reflects thorough research efforts and technical depth.