Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR21-008 | 1st February 2021 10:51

Random walks and forbidden minors III: poly(d/{\epsilon})-time partition oracles for minor-free graph classes

RSS-Feed




Revision #3
Authors: Akash Kumar, C. Seshadhri, Andrew Stolman
Accepted on: 1st February 2021 10:51
Downloads: 27
Keywords: 


Abstract:

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small {\epsilon} > 0, one removes {\epsilon}dn edges to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle, introduced by the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009).

A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. The partition oracle of Hassidim et al. runs in time d^poly(d/{\epsilon}) per query. They pose the open problem of whether poly(d/{\epsilon})-time partition oracles exist. Levi-Ron (ICALP 2013) give a refinement of the previous approach, to get a partition oracle that runs in time d^{\log(d/{\epsilon})-per query.

In this paper, we resolve this open problem and give \poly(d/{\epsilon})-time partition oracles for bounded degree graphs in any minor-closed family. Unlike the previous line of work based on combinatorial methods, we employ techniques from spectral graph theory. We build on a recent spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to develop efficient property testers.

A consequence of our result is a poly(d/{\epsilon})-query tester for any monotone and additive property of minor-closed families (such as bipartite planar graphs). Our result also gives poly(d/{\epsilon})-query algorithms for additive {\epsilon} n-approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families.



Changes to previous version:

Rendering issue again. Epsilons not rendered correctly earlier.


Revision #2 to TR21-008 | 1st February 2021 00:13

Random walks and forbidden minors III: poly(d/{\epsilon})-time partition oracles for minor-free graph classes





Revision #2
Authors: Akash Kumar, C. Seshadhri, Andrew Stolman
Accepted on: 1st February 2021 00:13
Downloads: 11
Keywords: 


Abstract:

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small {\epsilon} > 0, one removes {\epsilon}dn edges to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle, introduced by the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009).

A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. The partition oracle of Hassidim et al. runs in time d^poly(d/{\epsilon}) per query. They pose the open problem of whether poly(d/{\epsilon})-time partition oracles exist. Levi-Ron (ICALP 2013) give a refinement of the previous approach, to get a partition oracle that runs in time d^{\log(d/{\epsilon})-per query.

In this paper, we resolve this open problem and give \poly(d/{\epsilon})-time partition oracles for bounded degree graphs in any minor-closed family. Unlike the previous line of work based on combinatorial methods, we employ techniques from spectral graph theory. We build on a recent spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to develop efficient property testers.

A consequence of our result is a poly(d/{\epsilon})-query tester for any monotone and additive property of minor-closed families (such as bipartite planar graphs). Our result also gives poly(d/{\epsilon})-query algorithms for additive {\epsilon} n-approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families.?dn edges to get connected components of size independent of n. An important tool for sublinear
algorithms and property testing for such classes is the partition oracle, introduced by the seminal
work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure
that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a
query vertex v, the partition oracle outputs the component containing v in time independent of
n. All the answers are consistent with a single hyperfinite decomposition.
The partition oracle of Hassidim et al. runs in time d^poly(d/?)-per query. They pose the
open problem of whether poly(d/?)-time partition oracles exist. Levi-Ron (ICALP 2013) give
a refinement of the previous approach, to get a partition oracle that runs in time d^log(d/?)-per
query.
In this paper, we resolve this open problem and give poly(d/?)-time partition oracles for
bounded degree graphs in any minor-closed family. Unlike the previous line of work based on
combinatorial methods, we employ techniques from spectral graph theory. We build on a recent
spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to
develop efficient property testers. A consequence of our result is a poly(d/?)-query tester for
any property of minor-closed families (such as bipartite planar graphs). Our result also gives
poly(d/?)-query algorithms for additive ?n-approximations for problems such as maximum
matching, minimum vertex cover, maximum independent set, and minimum dominating set for
these graph families.



Changes to previous version:

Fixing the statement of theorem 1.3


Revision #1 to TR21-008 | 31st January 2021 08:08

Random walks and forbidden minors III: poly(d/{\epsilon})-time partition oracles for minor-free graph classes





Revision #1
Authors: Akash Kumar, C. Seshadhri, Andrew Stolman
Accepted on: 31st January 2021 08:08
Downloads: 23
Keywords: 


Abstract:

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small {\epsilon} > 0, one removes
{\epsilon}dn edges to get connected components of size independent of n. An important tool for sublinear
algorithms and property testing for such classes is the partition oracle, introduced by the seminal
work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure
that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a
query vertex v, the partition oracle outputs the component containing v in time independent of
n. All the answers are consistent with a single hyperfinite decomposition.
The partition oracle of Hassidim et al. runs in time d^poly(d/{\epsilon})-per query. They pose the
open problem of whether poly(d/{\epsilon})-time partition oracles exist. Levi-Ron (ICALP 2013) give
a refinement of the previous approach, to get a partition oracle that runs in time d^log(d/{\epsilon})-per
query.
In this paper, we resolve this open problem and give poly(d/{\epsilon})-time partition oracles for
bounded degree graphs in any minor-closed family. Unlike the previous line of work based on
combinatorial methods, we employ techniques from spectral graph theory. We build on a recent
spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to
develop efficient property testers. A consequence of our result is a poly(d/{\epsilon})-query tester for
any property of minor-closed families (such as bipartite planar graphs). Our result also gives
poly(d/{\epsilon})-query algorithms for additive {\epsilon}n-approximations for problems such as maximum
matching, minimum vertex cover, maximum independent set, and minimum dominating set for
these graph families.



Changes to previous version:

Fixing rendering of "epsilon" in the abstract


Paper:

TR21-008 | 30th January 2021 13:18

Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes





TR21-008
Authors: Akash Kumar, C. Seshadhri, Andrew Stolman
Publication: 30th January 2021 13:24
Downloads: 57
Keywords: 


Abstract:

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small ? > 0, one removes
?dn edges to get connected components of size independent of n. An important tool for sublinear
algorithms and property testing for such classes is the partition oracle, introduced by the seminal
work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure
that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a
query vertex v, the partition oracle outputs the component containing v in time independent of
n. All the answers are consistent with a single hyperfinite decomposition.
The partition oracle of Hassidim et al. runs in time d^poly(d/?)-per query. They pose the
open problem of whether poly(d/?)-time partition oracles exist. Levi-Ron (ICALP 2013) give
a refinement of the previous approach, to get a partition oracle that runs in time d^log(d/?)-per
query.
In this paper, we resolve this open problem and give poly(d/?)-time partition oracles for
bounded degree graphs in any minor-closed family. Unlike the previous line of work based on
combinatorial methods, we employ techniques from spectral graph theory. We build on a recent
spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to
develop efficient property testers. A consequence of our result is a poly(d/?)-query tester for
any property of minor-closed families (such as bipartite planar graphs). Our result also gives
poly(d/?)-query algorithms for additive ?n-approximations for problems such as maximum
matching, minimum vertex cover, maximum independent set, and minimum dominating set for
these graph families.



ISSN 1433-8092 | Imprint