Given a family @math of graphs and a positive integer @math , a graph @math is called vertex @math -fault-tolerant with respect to @math , denoted by @math -FT @math , if @math contains some @math as a subgraph, for every @math with @math . Vertex-fault-tolerance has been introduced by Hayes [A graph model for fault-tolerant computing systems, IEEE Transactions on Computers, C-25 (1976), pp. 875-884.], and has been studied in view of potential applications in the design of interconnection networks operating correctly in the presence of faults. We define the Fault-Tolerant Complete Matching (FTCM) Problem in bipartite graphs of order @math : to design a bipartite @math , with @math , @math , @math , that has a FTCM, and the tuple @math , where @math and @math are the maximum degree in @math and @math , respectively, is lexicographically minimum. @math has a FTCM if deleting at most @math vertices from @math creates @math that has a complete matching, i.e., a matching of size @math . We show that if @math is integer, solutions of the FTCM Problem can be found among @math -regular bipartite graphs of order @math , with @math , and @math . If @math then all @math -regular bipartite graphs of order @math have a FTCM, and for @math , it is not the case. We characterize the values of @math , @math , @math , and @math that admit an @math -regular bipartite graph of order @math , with @math , and give a simple construction that creates such a graph with a FTCM whenever possible. Our techniques are based on Hall's marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them.
Design of fault-tolerant bipartite graphs has potential applications in the design of flexible processes, where there are @math different request types and @math servers that should process them (see, for example, the work of @cite_0 for a review of the topic).
@cite_0
2031039901
Consider a large database of @math data items that need to be stored using @math servers. We study how to encode information so that a large number @math of read requests can be performed in parallel while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset Batch Codes introduced by Ishai, Kushilevitz, Ostrovsky and Sahai [17]. We give families of multiset batch codes with asymptotically optimal rates of the form @math and a number of servers @math scaling polynomially in the number of read requests @math . An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graph-theoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close to optimal tradeoffs between the parameters for bipartite graph based batch codes.