Oded's choices (Nr. 303)

Testing Hamiltonicity (and other problems) in Minor-Free Graphs

by Reut Levi and Nadav Shoshan

Oded's comments

As stated in the Feb'21 news of PT Review, although testing grqaph properties has been studied extensively in the dense graph model (see Chap 8 of my Intro to PT) and quite extensively in the bounded-degree graph model (see Chap 9), the general graph model (see Chap 10) has been studied much less. In particular, as reviewed in Section 1.2.3 of the current paper, most of the known results refer to inputs that are promised to be of a restricted form (e.g., be minor-free), and the current paper continues this line of research.

The main results, in my opinion, are the tester of Hamiltonicity and the local construction of an almost minimum weight spanning subgraph in minor-free grqaphs, in the general graph model. These $\poly(1/eps)$-query algorithms use the new partition oracle of Kumar, Seshadhri, and Stolman. Note that, although these oracles assume that the graph has bounded degree, they can be used in the current setting by effectively ignoring the few vertices of high degree.

In addition, this work presents improved testers for the bounded-degree graph model, while also assuming that the input graph is minor-free. These the improvements are obtained by using a relaxed notion of partition oracles, which suffices for the foregoing applications, and allows for a simpler and more query-efficient implementation.

The original abstract

In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In particular, we provide the following algorithms for minor-free unbounded degree graphs.

A tester for Hamiltonicity with two-sided error with poly(1/eps)-query complexity, where eps is the proximity parameter.
A local algorithm, as defined by Rubinfeld et al. (ICS 2011), for constructing a spanning subgraph with almost minimum weight, specifically, at most a factor (1+eps) of the optimum, with poly(1/eps)-query complexity.

Both our algorithms use partition-oracles, a tool introduced by Hassidim et al. (FOCS 2009), which are oracles that provide access to a partition of the graph such that the number of cut-edges is small and each part of the partition is small. The polynomial dependence in 1/eps of our algorithms is achieved by combining the recent poly(d/eps)-query partition oracle of Kumar-Seshadhri-Stolman (ECCC 2021) for minor-free graphs with degree bounded by d.

For bounded degree minor-free graphs we introduce the notion of covering partition oracles which is a relaxed version of partition oracles and design a poly(d/eps)-time covering partition oracle for this family of graphs. Using our covering partition oracle we provide the same results as above (except that the tester for Hamiltonicity has one sided error) for minor free bounded degree graphs, as well as showing that any property which is monotone and additive (e.g. bipartiteness) can be tested in minor-free graphs by making poly(d/eps)-queries.

The benefit of using the covering partition oracle rather than the partition oracle in our algorithms is its simplicity and an improved polynomial dependence in 1/eps in the obtained query complexity.

See arXiv 2102.11728

Back to list of Oded's choices.