ApproximateHypergraphPartitioningandApplications(2007)-计算机科学

170 浏览量 2021-04-22 18:09:01 上传评论收藏 350KB PDF 举报

资源推荐

资源详情

资源评论

Approximate Hypergraph Partitioning and Applications

∗

Eldar Fischer

†

Arie Matsliah

‡

Asaf Shapira

Abstract

Szemer´edi’s regularity lemma is a corner-stone result in extremal combinatorics. It (roughly)

asserts that any dense graph is composed of a ﬁnite number of pseudo-random graphs. The

regularity-lemma has found many applications in theoretical computer-science and thus a lot of

attention was given to designing algorithmic versions of this lemma. Our main results in this

paper are the following:

• We introduce a new approach to the problem of constructing regular partitions of graphs,

which results in a surprisingly simple O(n) time algorithmic version of the regularity lemma,

thus improving over the previous O(n

) time algorithms. Furthermore, unlike all the previ-

ous approaches for this problem [3, 10, 14, 15, 21], which only guaranteed to ﬁnd partitions

of tower-size, our algorithm will ﬁnd a small regular partition, if one exists in the graph.

• For any constant r ≥ 3 we give an O(n) time randomized algorithm for constructing regular

partitions of r-uniform hypergraphs, thus improving the previous O(n

2r−1

) time (determin-

istic) algorithms [8, 15].

The above results are obtained as an application of an eﬃcient algorithm for approximating

partition-problems of hypergraphs which we obtain here.

• Given a (directed) hypergraph with bounded edge arities, a set of constraints on the set

sizes and densities of a possible partition of its vertex set, and an approximation parameter,

we provide in O(n) time a partition approximating the constraints if a partition satisfying

them exists. We can also test in O(1) time for the existence of such a partition given the

approximation parameter.

This algorithm extends the result of Goldreich, Goldwasser and Ron for graph partition prob-

lems [16], and encompasses more recent hypergraph related results such as the maximal constraint

satisfaction approximation of [5].

∗

A preliminary version of this paper appeared in Proc. of the 48

Annual IEEE Symposium on Foundations of

Computer Science (FOCS) 2007, 579-589.

†

Faculty of Computer Science, Technion – Israel institute of technology, Technion City, Haifa 32000, Israel. Email:

eldar@cs.technion.ac.il. Research supported in part by an ISF grant number 1011/06.

‡

CWI, Amsterdam. Email: ariem@cwi.nl.

Georgia Institute of Technology. Email: asaﬁco@math.gatech.edu. Research supported by NSF grant DMS-

0901355.

1 Introduction and General Background

1.1 Background on Szemer´edi’s regularity lemma

The regularity lemma of Szemer´edi [26] is one of the most important results in graph theory. It

guarantees that any dense graph can be partitioned into a bounded number of bipartite graphs that

are “pseudo-random”. In other words, the lemma guarantees that every graph has an ²-approximation

of constant descriptive size. This fact is very useful in many applications since dealing with random-

like graphs is much easier than dealing with arbitrary graphs. It is far from surprising that a lemma

that supplies an approximation of constant size for arbitrarily large graphs will also have algorithmic

applications. The original proof of the regularity lemma was non-constructive, in the sense that it

did not supply an eﬃcient polynomial time algorithm for obtaining a regular partition of the graph.

The ﬁrst polynomial time algorithm for constructing such a partition of a graph was obtained by

Alon et al. [2]. Additional algorithmic versions of the lemma were later obtained in [3, 10, 14, 15, 21].

For a comprehensive survey of the applications of the lemma, the interested reader is referred to [22].

Before stating the regularity lemma we need some basic notation. For two nonempty disjoint

vertex sets A and B of a graph G, we deﬁne E(A, B) to be the set of edges of G between A and

B. The edge density of the pair is deﬁned by d(A, B) = |E(A, B)|/(|A||B|). We use the notation

a = b ± c as a shorthand for b − c ≤ a ≤ b + c. The original notion of regularity, to which we refer

to as subset regularity, is deﬁned as follows.

Deﬁnition 1.1 (²-subset-regular pair) A pair (A, B) is ²-subset-regular if for every A

⊆ A and

⊆ B satisfying |A

| ≥ ²|A| and |B

| ≥ ²|B|, we have d(A

, B

) = d(A, B) ± ².

Note that a random bipartite graph with a positive edge density is o(1)-subset-regular with high

probability. Thus, the smaller ² is, the more “random”-like an ²-subset-regular pair is.

A partition V

, . . . , V

of the vertex set of a graph is called an equipartition if |V

| and |V

| diﬀer

by no more than 1 for all 1 ≤ i < j ≤ k (so in particular every V

has one of two possible sizes).

The order of an equipartition denotes the number of partition classes (k above). An equipartition

, . . . , V

of the vertex set of a graph is called ²-subset-regular if all but at most ²

of the pairs

, V

) are ²-subset-regular. Szemer´edi’s regularity lemma can be formulated as follows.

Lemma 1.2 ([26]) For every ² > 0 there exists T = T

1.2

(²), such that any graph with n ≥ 1/²

vertices has an ²-subset-regular equipartition of order

k, where 1/² ≤

k ≤ T .

We now deﬁne an equivalent notion of regularity. Given (A, B), we denote by d

(A, B) the

density of C

instances (cycles of size 4) between A and B, namely, the number of copies of C

whose

vertices alternate between A and B, divided by their possible maximum number

|A|

¢¡

|B|

When counting the number of C

instances between A and B we only consider the edges connecting A and B.

Therefore, 0 ≤ d

(A, B) ≤ 1.

Deﬁnition 1.3 (²-locally-regular pair and partition) A pair (A, B) of vertex sets is ²-locally-

regular if d

(A, B) = (d(A, B))

± ².

An equipartition V

, . . . , V

of the vertex set of a graph is called ²-lo cally-regular if all but at most

of the pairs (V

, V

) are ²-locally-regular.

In the sequel we will refer to local-regularity simply as regularity whenever there is no ambiguity

in the context. The main observation about this deﬁnition is that an ²

O(1)

-regular pair is also ²-

subset-regular, and the other direction similarly holds. This was ﬁrst proved in [2]. Our algorithm

will center on ﬁnding partitions in which the pairs conform to local regularity.

The proof of the regularity lemma is fairly simple. One starts with any partition of the vertices of

the input graph into k = 1/² sets V

, . . . , V

. If this partition is ²-regular then we are done. Otherwise,

there are many pairs (V

, V

) which are not ²-regular. For any such pair V

, V

, there are thus

two

subsets U

⊆ V

and U

⊆ V

such that d(U

, U

) 6= d(V

, V

) ± ². One then shows how to use the

collection of pairs (U

, U

) in order to reﬁne the partition V

, . . . , V

into a new partition V

, . . . , V

in such a way that a certain potential function increases by at least ²

. Since this potential function

is bounded from above by 1 this process must terminate after 1/²

steps. The only non-constructive

part of this proofs is the task of ﬁnding the pairs (U

, U

). Therefore, the most natural way to obtain

an algorithmic version of the regularity lemma is to ﬁnd a polynomial time algorithm for solving this

problem. Indeed, all the previous algorithmic versions of the regularity lemma [3, 10, 14, 15, 21] used

this scheme; they only diﬀered in the details on how one ﬁnds the pairs (U

, U

). The ﬁrst polynomial

time algorithm given by Alon et. al [2] was based on Boolean matrix multiplication. The algorithm

of Frieze and Kannan [14] used singular value decomposition. The algorithm of Alon and Naor was

based on an approximation algorithm for the cut-norm [3]. Finally, the algorithm of Kohayakawa,

R¨odl and Thoma [21] was based on performing random walks on expanders, being the ﬁrst to obtain

a running time of O(n

As is well known, the main drawback of the regularity lemma is that the bounds that the

lemma guarantees have an enormous dependence on ². More precisely, denote the tower function by

Tower(i) = 2

Tower(i−1)

= 2

. Then the bounds on T

1.2

(²) are given by Tower(1/²

). Furthermore,

Gowers [17] proved that these bounds are not far from the truth (in the qualitative sense), as he

constructed a graph that has no ²-regular partition of size less than Tower(1/²

1/16

All previous algorithmic versions of the regularity lemma had two drawbacks due to their shared

principles. First, since they reprove the regularity lemma algorithmically, they could only be guaran-

teed to ﬁnd the worst-case regular partition. By the result of Gowers [17] mentioned above, this worst

case partition can be of size Tower(1/²). Therefore, even if the graph has a small regular partition

these algorithms are only guaranteed to return a partition of size Tower(1/²). Second, although the

regularity lemma is approximative in nature, these algorithms traditionally read the entire graph to

By the equivalence between the two notions of regularity we have deﬁned above.

provide the partition, making their running time equal to Ω(n

) or worse for a ﬁxed ².

1.2 A new approach for the constructive regularity lemma

In this paper we take a completely diﬀerent approach to the problem of constructing a regular

partition. Instead of algorithmically proving the lemma, we take the lemma “for granted” and

design an algorithm for checking if a graph has a regular partition with a certain number of classes.

Thus, our algorithm will ﬁnd a small partition in the graph if one exists, as opp osed to all previous

algorithms, who can only guarantee to ﬁnd the worst case partition of size Tower(1/²). Our second

improvement over the previous O(n

) algorithms is that the running time of our algorithm is O(n)

for any ﬁxed ². Additionally, even the hidden constants in the O(n) running time will only depend

on the size of the smallest regular partition. Note that this running time is sub-linear in the size of

the input (which is O(n

)), and is optimal as it is linear in the output size – just “writing down” a

partition of the vertices takes O(n) time.

Theorem 1 (Main Result) There is a randomized algorithm, that given ² > 0 and an n vertex

graph G, that has a

²-regular partition of order

k ≥ 1/²,

produces with high probability an ²-regular

partition of G of order k, where 1/² ≤ k ≤

k. The expected running time of the algorithm is

n · poly(

k) + 2

poly(

. (1)

Additionally, if only the densities of the regular partition rather than the partition itself need to be

produced, then this can be done in time 2

poly(

We stress that in Theorem 1, the algorithm does not receive the number

k as part of the input.

Also, the hidden constants in the running time are absolute and do not depend on ² or

k, and

correspondingly there is no unconditional Tower-dependence on ² as in the previous algorithms.

As it turns out, a simple inspection of the proof we provide can show that the constant

in the

regularity parameter can be replaced by any constant smaller than 1; we just use the constant

for

maintaining the simplicity of the presentation. Although the algorithm does not know

k in advance,

its running time does depend, in a good sense, on

k. That is, if

k is small then the running time of

the algorithm will also be small, compared to the unconditional Tower-type dependence on ² of the

previous algorithms.

An interesting aspect of our new algorithmic version of graph regularity is that it is obtained as

a simple application of a general hypergraph partitioning algorithm which we construct in this paper.

This aspect of the paper is discussed in the next subsection.

The reason for the requirement that

k ≥ 1/² is that the same requirement is needed in Lemma 1.2. For the same

reason we return a partition of size k ≥ 1/².

1.2.1 Hypergraph regularity

Similarly to graphs, (weak) subset-regularity for r-tuples of vertex sets in r-uniform hypergraph is

deﬁned as not admitting large subsets U

⊆ V

, . . . , U

⊆ V

so that the edge densities of V

, . . . , V

and U

, . . . , U

diﬀer greatly. Regular partitions of hypergraphs are then deﬁned in an analogous

manner to that of graphs.

Our main technical tool of hypergraph partitioning is also useful in ﬁnding (weakly) regular

partitions of r-uniform hypergraphs, when combined with some ideas similar to [12]. For any ﬁxed

r and ², we design an O(n) time (randomized) algorithm for ﬁnding an ²-regular partition of an r-

uniform hypergraph. In this case the improvement in the running time is more substantial compared

to the previous algorithms, whose running time was O(n

2r−1

). However, as opposed to the graph

case, in this case our algorithm is not guaranteed to ﬁnd small partitions if they exist.

1.3 Hypegraph partition problems

Graph partition problems are some of the most well-studied problems both in graph theory and

in computer-science. Standard examples of partition problems include k-colorability, Max-Clique

and Max-Cut. Most of these problems are computationally hard even to approximate, but it was

observed in the 90’s [6, 11] that many of these partition problems have good approximations when

the input graph is dense. The main tool that we develop in this paper is an eﬃcient O(n) algorithm

for partitioning hypergraphs, with an accompanying O(1)-query test for the existence of a partition

with given parameters.

Our framework for studying hypergraph partition problems generalizes the framework of graph

partition problems that was introduced by Goldreich, Goldwasser and Ron [16]. Let us brieﬂy discuss

the graph partitioning algorithm of [16]. A graph partition-instance Ψ is composed of an integer k

specifying the number of sets in the required partition V

, . . . , V

of the graph’s vertex set, and

intervals specifying the allowed ranges for the number of vertices in every V

and the number of

edges between every V

and V

for i ≤ j. Goldreich, Goldwasser and Ron [16] showed that for any

partition-instance Ψ with k parts, and for any positive ², there is an (2

(k/²)

O(k)

+ (k/²)

O(k)

n)-time

algorithm that produces a partition of an input graph that is ²-close to satisfying Ψ, assuming that

a satisfying partition exists (the distance is measured by the diﬀerences b etween the actual edge-

densities and the required ones). Note that one can formulate many problems, such as k-colorability,

Max-Cut and Max-Clique, in this framework of partition-instances. Therefore, the algorithm of

[16], which we will henceforth refer to as the GGR-algorithm, implies

for example that there is an

O(1/²

)

+ n/²

)-time algorithm that approximates the size of the maximum cut of a graph to within

an additive error of ²n

. It also implies that for any ² > 0 there is an (2

O(1/²

)

+n/²

)-time algorithm

To be precise, the exact bounds we quote for Max-Cut and 3-colorability follow from a more specialized argument

given in [16] and not directly from the general GGR-algorithm. See [16] for more details.

剩余36页未读，继续阅读

评论收藏

内容反馈

weixin_38721652

粉丝: 3
资源: 935

Approximate Hypergraph Partitioning and Applications (2007)-计算机科...

最新资源

Approximate Hypergraph Partitioning and Applications (2007)-计算机科...

The Longest Common Extension Problem Revisited and Applications to Approximate String Searching (2010)-计算机科学

ApEn.rar_apen_approximate_approximate entropy_non-stationary

Approximate affine linear relationship between L-1 norm objective function values and L-2 norm constraint bounds

Approximate-Message-Passing-master_amp.zip

Approximate-Message-Passing-master_amp_源码.zip

the art of approximate in science and engineering

Cache, Hash and Space-Efficient Bloom Filters-计算机科学

On the k-Independence Required by Linear Probing and Minwise Independece - December 25th, 2014 (1302.5127)-计算机科学

Approximate String Matching和Lock-Free Data Structures

论文研究-A very fast large scale BSS algorithm by joint approximate diagonalization of simplified cumulant matrices.pdf

Computing and Combinatorics

Improved Fast Similarity Search in Dictionaries - 2010 (1008.1191v2)-计算机科学

Best Approximate Solution of Matrix EquationAXB CYD=E

Theory of Locality Sensitive Hashing - CS246 Stanford (Slides)-计算机科学

A Locality-Sensitive Hash for Real Vectors (10.1.1.215.7690)-计算机科学

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

XCP协议的规范文档

GD32替换STM32注意事项.pdf

NPPJSONViewer.zip

蓝牙BLE协议中文版.pdf

CANoe通过CAPL脚本实现自动测试

AD20官方中文教程.pdf

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）