A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and induced matching numbers are defined as the maximum cardinality of such matchings, respectively, and are known to be NP-hard to compute. In this paper, we study the relationship between these two parameters and the matching number. In particular, we discuss the complexity of two decision problems; first: deciding if the matching number and disconnected matching number are equal; second: deciding if the disconnected matching number and induced matching number are equal. We show that given a bipartite graph with diameter four, deciding if the matching number and disconnected matching number are equal is NP-complete; the same holds for bipartite graphs with maximum degree three. We characterize diameter three graphs with equal matching number and disconnected matching number, which yields a polynomial time recognition algorithm. Afterwards, we show that deciding if the induced and disconnected matching numbers are equal is co-NP-complete for bipartite graphs of diameter 3. When the induced matching number is large enough compared to the maximum degree, we characterize graphs where these parameters are equal, which results in a polynomial time algorithm for bounded degree graphs.

ABSTRACT Introduction An XOR filter is a probabilistic data structure representing a set of keys for membership queries. Given a set of keys, and hash functions , the filter relies on filling in an array such that, for all , equals a special value, called the fingerprint of . A common approach to fill in is by using a greedy algorithm, which may or may not succeed, and whose probability of failing increases as the load factor increases. The Spatial XOR filter is a variant proposing that the hash functions map each key only into a smaller contiguous portion of , called window, and empirical results show that it is possible to achieve a larger for the same chance of succeeding in filling in using the greedy approach. A result in the literature conjectures that the optimal window size is for . Methods In this work, we comprehensively test this conjecture, considering various values of and . Using the leave‐one‐out validation process of machine learning, and Occam's razor principle, to determine the optimal window size and maximum load factor as a function of . Results We find that the optimal window size of is confirmed by our methodology, and we provide the concrete function behind the asymptotic notation; as a byproduct of the methodology, we suggest alternative candidate functions for this window optimal size. We also propose the maximum load factor function possible to achieve in terms of . Conclusions Using the optimal window size empirically provided by our methodology, the results show that the Spatial XOR filter is competitive among its peers. Other filters have very close space savings compared to the Spatial XOR filter. The derived functions extrapolated well in the experiments, although the theoretical optimal window size remains an open problem.