没有合适的资源?快使用搜索试试~ 我知道了~
顶点覆盖参考论文(英文)1
需积分: 0 0 下载量 199 浏览量
2022-08-03
15:03:42
上传
评论
收藏 218KB PDF 举报
温馨提示
试读
20页
顶点覆盖参考论文(英文)1
资源详情
资源评论
资源推荐
Approximating the Minimum Vertex Cover in Sublinear Time and
a Connection to Distributed Algorithms
Michal Parnas
School of Computer Science
The Academic College of Tel-Aviv-Yaffo
Tel-Aviv, Israel
Dana Ron
∗
Department of EE – Systems
Tel-Aviv University
Ramat Aviv, Israel
Abstract
For a given graph G over n vertices, let OPT
G
denote the size of an optimal solution in G
of a particular minimization problem (e.g., the size of a minimum vertex cover). A randomized
algorithm will be called an α-approximation algorithm with an additive error for this minimiza-
tion problem, if for any given additive error parameter > 0 it computes a value
]
OPT such
that, with probability at least 2/3, it holds that OPT
G
≤
]
OPT ≤ α · OPT
G
+ n .
Assume that the maximum degree or average degree of G are bounded. In this case, we show
a reduction from local distributed approximation algorithms for the vertex cover problem to
sublinear approximation algorithms for this problem. This reduction can be modified easily and
applied to other optimization problems that have local distributed approximation algorithms,
such as the dominating set problem.
We also show that for the minimum vertex cover problem, the query complexity of such
approximation algorithms must grow at least linearly with the average degree
¯
d of the graph.
This lower bound holds for every multiplicative factor α and small constant as long as
¯
d =
O(n/α). In particular this means that for dense graphs it is not possible to design an algorithm
whose complexity is o(n).
Keywords. Sublinear approximation algorithms, distributed algorithms, minimum vertex cover.
∗
This research was supported by the Israel Science Foundation (grant number 89/05).
1 Introduction
As the need for computers to process massive data sets increases, the need for sublinear time (or
space) algorithms becomes evident. In recent years efforts were made to design sublinear algorithms
for a variety of basic computational problems and in two main frameworks: the sublinear-space
algorithms associated with the streaming model (see [22] for a survey) and the sublinear-time
algorithms associated with the framework of property testing [24, 11] (see [10, 8, 23] for surveys).
We note that sublinear time algorithms were presented also outside the domain of property testing.
Notable examples include the sublinear-time algorithms for estimating the size of a minimum
spanning tree of a graph (e.g., [2, 4]) and the sublinear-time algorithms for clustering (e.g., [14, 21,
5]).
In this paper we further the study of sublinear-time algorithms for combinatorial optimization
problems that are NP-hard and for which polynomial-time approximation algorithms are known. A
typical example is the minimum vertex cover problem. The factor-two approximation algorithm
of Gavril (cf. [9]) is one of the jewels of computer science. This algorithm runs in linear time
and provides a relatively good approximation to a problem that is NP-hard to optimize or even to
approximate up to a factor of 1.3606 [6]. We note also that Khot and Regev [16] showed, based on
the unique games conjecture, that the size of a minimum vertex cover is hard to approximate to
within 2−γ, for any constant γ. Given that approximation seems unavoidable if we seek an efficient
algorithm (i.e., one running in polynomial-time), can we obtain any non-trivial approximation in
sublinear time?
Needless to say, the study of sublinear-time algorithms requires a specification of the way
the algorithm obtains portions of the input. We follow the standard conventions by which such
algorithms are modeled as oracle machines that may make neighborhood queries. Specifically, the
query (v, i) is answered with the i-th neighbor of vertex v or with a special symbol in case v has less
than i neighbors. We also allow degree queries, that is, the algorithm may query for every vertex
v what is its degree
1
.
1.1 Our Results
It is easy to see that a sublinear-time approximation for problems such as the minimum vertex
cover problem, is not possible if we insist on the standard notion of a relative approximation (e.g.,
a factor two approximation). The reason being that such a relative approximation algorithm should
obtain a good approximation even in the case that the optimum solution is tiny (e.g., the minimum
vertex cover is a singleton). We thus relax the definition by allowing an additional additive error
that is related to the optimum solution of a worst-case instance (e.g., the minimum vertex cover of
a clique). This notion is formalized next.
Relative approximation with an additive error. For a given a graph G over n vertices, let
OPT
G
denote the size of an optimal solution in G of some minimization problem (e.g., the size of
a minimum vertex cover). We say that a value
]
OPT is an (α, )-estimate of OPT
G
if
OPT
G
≤
]
OPT ≤ α · OPT
G
+ n.
1
Clearly it is possible to replace each degree query by at most d neighbor queries, where d is the maximum degree
of the graph. However, for the sake of simplicity we allow our algorithms also degree queries.
1
In the case of maximization problems we require that OPT
G
/α − n ≤
]
OPT ≤ OPT
G
.
An algorithm that is given > 0 as an input parameter and computes with probability at
least 2/3 an (α, )-estimate of OPT
G
for some value of α, is an α-approximation algorithm with
an additive error. Note that is a parameter to the algorithm, whereas α is determined by the
capabilities of the specific algorithm. For the sake of succinctness, whenever there is no cause for
confusion, we use the term α-approximation algorithm, with the understanding that the algorithm
is allowed an additive error.
We focus on the query complexity of such approximation algorithms. The running time of the
algorithms we present is polynomial in the query complexity, and the lower bounds on the query
complexity hold without any computational assumptions.
A reduction from local distributed algorithms. We show a reduction from local distributed
approximation algorithms to sublinear approximation algorithms. The term distributed algorithms
refers to the computation of processors that are connected via a communication network, and the
term local refers to such algorithms that use a small number of communication rounds. Thus,
during a computation of such a local algorithm, each processor can only obtain information from
its “close” vicinity.
We consider local distributed algorithms that approximate a global function f (G) of the graph,
where f(G) is the optimum, taken over all admissible subsets of vertices (e.g., vertex covers of
G), of a (bounded) weighted sum of quantities associated with the individual vertices. We observe
that a good approximation of f(G) can be obtained in sublinear time by selecting a few vertices at
random and emulating the distributed algorithm only for them (This requires a partial emulation
also of their vicinities.). Below we demonstrate this idea for the case of the minimum vertex cover.
Let G be a distributed network with n nodes and degree at most d, and let D be a (possibly
randomized) distributed algorithm that computes in k rounds a vertex cover C such that, with
high (constant) probability, |C| ≤ α · VC
G
, where VC
G
is the size of a minimum vertex cover in
the graph, and α > 1. Then, we obtain a randomized sublinear α-approximation algorithm that
outputs an estimate
g
VC, such that with probability at least 2/3:
VC
G
≤
g
VC ≤ α · VC
G
+ n .
The query complexity of the sublinear algorithm is O(d
k
/
2
).
Applications of the reduction. To demonstrate the applicability of this reduction we present
a very simple approximate distributed algorithm for the minimum vertex cover problem, and show
how using our reduction we can get a sublinear (2 log d + 1)-approximation algorithm for the size
of the minimum vertex cover. The query complexity of this sublinear algorithm is O(d
log d
/
2
).
Using our reduction and the distributed algorithm of Kuhn, Moscibroda, and Wattenhofer [17] for
the minimum vertex cover we can get a c-approximation algorithm, where c > 2, using d
O(log d)
/
2
queries. To obtain a 2-approximation algorithm, the number of queries performed is d
O(log(d)/
3
)
.
By applying the reduction to a recent result of Marko [19] it is possible to get a 2-approximation
algorithm by performing d
O(log(d/))
queries.
We can apply the reduction to other optimization problems as well. The first observation is that
we can use the sublinear approximation algorithm for the minimum vertex cover to approximate the
size of the maximum matching of a graph, since for any maximum matching M and any minimum
2
vertex cover C it holds |M| ≤ |C| ≤ 2|M|. In addition, using the local distributed algorithm
in [17], we can get an O(log d)-approximation algorithm for the minimum size of a dominating
set using d
O(log d)
/
2
queries. Similar results can be obtained based on [17] for other covering and
packing problems, such as finding the size of a minimum edge-cover of all isomorphic instances of
a given subgraph. This covering problem was also studied by Marko and Ron [20] who built on the
approach presented in this paper.
An improved reduction. The complexity of emulating k rounds of a distributed algorithm at
a vertex in a graph of maximum degree d grows like d
k
. We observe that, in many cases, we
may suspend the emulation whenever we encounter a vertex of degree significantly greater than
the average degree
¯
d. In these cases (which include the minimum vertex cover problem and the
minimum dominating set problem), the dependence on d can be replaced by O(min{d,
¯
d/}), where
the complexity is bounded in expectation. Furthermore, the algorithm does not need to be given d
nor
¯
d as input, and the same complexity can be obtained if only neighbor queries (but not degree
queries) are allowed.
A lower bound. Complexities that grow with the graph degree (or the average degree) seem
essential to our approach. In contrast, in property testers for bounded-degree (and general sparse)
graphs, the complexity many times decreases when the graph becomes dense (see, e.g., [12, 15]
and [11, 1]). This raises the question of whether the complexity of approximation algorithms for
the minimum vertex cover needs to grow with the degree. We show that the answer is affirmative.
Specifically, we show that Ω(
¯
d) queries are necessary for any α-approximation algorithm (with an
additive error < 1/4) for VC
G
, as long as
¯
d = O(n/α). The lower bound holds even if we allow
also vertex-pair queries, on top of the standard neighborhood queries. That is, for any pair of
vertices u, v, the algorithm may query whether (u, v) is an edge in the graph.
1.2 Other Related Work
The minimum vertex cover problem was previously considered in the context of property testing
(of bounded-degree graphs) [12]. In this context, the question is whether an algorithm can decide
in sublinear time and with high probability whether a graph has a vertex cover of a certain size ρn
or whether it is -far from having a vertex cover of this size. The latter means that more than ·dn
edges must be removed from the graph so that it have a vertex cover of size ρn. It was observed
in [12] that the NP-hardness results for approximating the minimum vertex cover, imply that this
task is hard as well.
In the case of bounded-degree graphs, one can view our formulation of the sublinear approxima-
tion problem for the minimum vertex cover as an extension of the property testing task. Namely,
the goal is to distinguish between the case that the graph has a vertex cover of size ρn and the case
in which it is -far from having a vertex cover of size α · ρn. However, we believe that our view of
the problem as an approximation of the size of the vertex cover, where both a multiplicative and
an additive error are allowed, is more natural.
Bogdanov, Obata and Trevisan [1] considered the question of obtaining lower bounds on the
query complexity of sublinear approximation algorithms for the minimum vertex cover problem
(that is, putting computational issues aside). They showed that every approximation algorithm
for the minimum vertex cover that outputs an estimate with a multiplicative error of at most 7/6,
3
剩余19页未读,继续阅读
大头蚊香蛙
- 粉丝: 17
- 资源: 317
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0