共查询到20条相似文献,搜索用时 15 毫秒
1.
k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that
it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard
to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second
result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors.
Received April 11, 1997/Revised June 10, 1999 相似文献
2.
Bojan Mohar 《Combinatorica》2001,21(3):395-401
It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson.
Received July 6, 1998
RID="*"
ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98. 相似文献
3.
linear array network consists of k+1 processors with links only between and (0≤i<k). It is required to compute some boolean function f(x,y) in this network, where initially x is stored at and y is stored at . Let be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, , where D(f) is the standard two-party communication complexity of f. Tiwari proved that for almost all functions and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite family of functions for which is essentially at most . Our construction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, given the least number of monochromatic rectangles in any partition of the input space. How tight are such bounds? We exhibit certain functions, for which the (two-party) communication complexity is twice as large as the best lower bound obtainable this way. Received: March 1, 1996 相似文献
4.
Amnon Ta-Shma 《Combinatorica》2002,22(1):123-145
A disperser is a bipartite graph with the property that every subset A of of cardinality at least K, has at least fraction of the vertices of as neighbors. Such graphs have many applications in derandomization. Saks, Srinivasan and Zhou presented an explicit construction
of a disperser with an almost optimal degree , for every . We extend their result for every parameter .
Received November 12, 1998/Revised June 20, 2000
RID="*"
ID="*" This work was partially done while the author was at the Department of Computer Science, Weizmann Institute of Science,
Rehovot, Israel. This work was supported by a Phil Zacharia postdoctoral fellowship. 相似文献
5.
, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes.
1. monotone-NC ≠ monotone-P.
2. For every i≥1, monotone-≠ monotone-.
3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone
Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const).
Only a separation of monotone- from monotone- was previously known.
Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART
games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get
lower bounds for the monotone depth of many functions. In particular, we get the following bounds:
1. For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result.
2. For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known.
Received: December 19, 1997 相似文献
6.
Dedicated to the Memory of Paul Erdős
We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan,
and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities
(in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable
from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the
basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer
jumping function.
Received November 12, 1998
RID="*"
ID="*" Supported in part by NSA grant MSPR-96G-184.
RID="†"
ID="†" Supported in part by an NSF Graduate Fellowship. 相似文献
7.
Improved Pseudorandom Generators for Combinatorial Rectangles 总被引:1,自引:0,他引:1
Chi-Jen Lu 《Combinatorica》2002,22(3):417-434
We construct a pseudorandom generator which uses bits and approximates the volume of any combinatorial rectangle in to within error. This improves on the previous construction using bits by Armoni, Saks, Wigderson, and Zhou [4]. For a subclass of rectangles with at most nontrivial dimensions and each dimension being an interval, we also give a pseudorandom generator using bits. This again improves the previous upper bound by Chari, Rohatgi, and Srinivasan [5].
Received July 29, 1998 相似文献
8.
Michele Conforti Gérard Cornuéjols Grigor Gasparyan Kristina Vušković 《Combinatorica》2002,22(1):19-33
We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous
pairs.
Received December 13, 1999
RID="*"
ID="*" This work was supported in part by the Fields Institute for Research in Mathematical Sciences, Toronto, Canada, and
by NSF grants DMI-0098427 and DMI-9802773 and ONR grant N00014-97-1-0196. 相似文献
9.
Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product).
Received August 31, 1998/Revised April 19, 2000
RID="†"
ID="†" Supported by NSERC of Canada Grant #691325. 相似文献
10.
d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v'. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given
distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their
incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors.
In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs.
Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that
these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices
can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and
(2) each subset itself exhibits a certain mixing property that is useful in our analysis.
Received: February 6, 1998 相似文献
11.
Quick Approximation to Matrices and Applications 总被引:1,自引:0,他引:1
m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997 相似文献
12.
Carsten Thomassen 《Combinatorica》2001,21(3):417-443
We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of in which each edge of corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang. Received May 26, 1998 相似文献
13.
Oded Goldreich Shafi Goldwasser Eric Lehman Dana Ron Alex Samorodnitsky 《Combinatorica》2000,20(3):301-337
at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions. Received March 29, 1999 相似文献
14.
Ron Aharoni 《Combinatorica》2001,21(1):1-4
We prove that in a tripartite 3-graph . Received March 17, 1999 相似文献
15.
Kamal Jain 《Combinatorica》2001,21(1):39-60
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges
in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as
the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively
rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge
gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem.
Received March 6, 1998 相似文献
16.
The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős.
Received July 12, 1999 相似文献
17.
Martin Grohe 《Combinatorica》1999,19(4):507-532
of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ).
The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement
method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs
can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each .
Received: March 23, 1998 相似文献
18.
In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is
analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing.
In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing
protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information.
Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for
routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols
known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously
introduced by the authors for designing compact routing protocols.
Received July 18, 1997 相似文献
19.
Y. Katznelson 《Combinatorica》2001,21(2):211-219
Dedicated to the memory of Paul Erdős In 1987 Paul Erdős asked me if the Cayley graph defined on Z by a lacunary sequence has necessarily a finite chromatic number. Below is my answer, delivered to him on the spot but never published, and some additional remarks. The key is the interpretation of the question in terms of return times of dynamical systems. Received February 7, 2000 相似文献
20.
Gohar M. M. Kyureghyan 《Combinatorica》2001,21(3):449-453
Motivated by some applications in computational complexity, Razborov and Vereshchagin proved a degree bound for cross-intersecting
families in [1]. We sharpen this result and show that our bound is best possible by constructing appropriate families. We
also consider the case of cross-t-intersecting families.
Received October 28, 1999 相似文献