We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction (CSP) formulation of these problems. 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.
For three-coloring, we know of several relevant references. Lawler @cite_15 is primarily concerned with the general chromatic number, but he also gives the following very simple algorithm for 3-coloring: for each maximal independent set, test whether the complement is bipartite. The maximal independent sets can be listed with polynomial delay @cite_5 , and there are at most @math such sets @cite_21 , so this algorithm takes time @math . Schiermeyer @cite_18 gives a complicated algorithm for solving 3-colorability in time @math , based on the following idea: if there is one vertex @math of degree @math then the graph is 3-colorable iff @math is bipartite, and the problem is easily solved. Otherwise, Schiermeyer performs certain reductions involving maximal independent sets that attempt to increase the degree of @math while partitioning the problem into subproblems, at least one of which will remain solvable. Our @math bound significantly improves both of these results.
@cite_5 @cite_15 @cite_21 @cite_18
2007940874 2007200873 2013568176 1526568622
This paper describes efficient deterministic techniques for breaking symmetry in parallel. These techniques work well on rooted trees and graphs of constant degree or genus. The primary technique allows us to 3-color a rooted tree in @math time on an EREW PRAM using a linear number of processors. These techniques are used to construct fast linear processor algorithms for several problems, including the problem of @math -coloring constant-degree graphs and 5-coloring planar graphs. Lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs are also proved. The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets @math and @math , where @math is an independent set and @math induces a forest. The set @math in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2. This paper addresses the cornerstone family of in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the @math nodes can only send @math -bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in @math rounds, where @math is the diameter of the graph. The best known running time in terms of @math alone is @math , which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based @math -round algorithm, where @math is the maximal degree in the graph. On the way to obtaining the above, we show that in the model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in @math rounds. , where @math is the maximum degree. When @math , the bound improves to @math and holds also for @math -coloring. In addition, we deterministically construct a @math -spanner with @math edges in @math rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a @math -spanner with @math edges runs in @math rounds. We give a new proof showing that it is NP-hard to color a 3-colorable graph using just 4 colors. This result is already known , [S. Khanna, N. Linial, and S. Safra, Combinatorica, 20 (2000), pp. 393--415], but our proof is novel because it does not rely on the PCP theorem, while the known one does. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor @math hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem [M. Bellare, O. Goldreich, and M. Sudan, SIAM J. Comput., 27 (1998), pp. 805--915]. Another aspect in which our proof is novel is in its use of the PCP theorem to show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs (this hardness result does not seem to follow from the earlier reduction of Khanna, Linial, and Safra). We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires @math colors. Our proof technique also shows that there is an @math such that it is NP-hard to legally 4-color even a @math fraction of the edges of a 3-colorable graph. Given two graphs @math and @math , the Subgraph Isomorphism problem asks if @math is isomorphic to a subgraph of @math . While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time @math using the color-coding technique of Alon, Yuster, and Zwick; (2) in time @math using Courcelle's Theorem; (3) in time @math using a result on first-order model checking by Frick and Grohe; or (4) in time @math for connected @math using the algorithm of Matou s ek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of @math and @math (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time [ f_1(p_1,p_2,..., p_ ) n^ f_2(p_ +1 ,..., p_k) ] exist, where each of @math is one of the 10 parameters depending only on @math or @math . We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of @math gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when @math is a bounded-degree tree of constant pathwidth and @math is a planar graph of bounded pathwidth. This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data.Three results are proved within this model: • A 3-coloring of an n-cycle requires time @math . This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most @math requires at least @math colors. • In an n-vertex graph of largest degree @math , an @math -coloring may be found in time @math . Let @math be a graph with a threshold function @math such that @math for every vertex @math of @math , where @math is the degree of @math in @math . Suppose we are given a target set @math . This paper considers the following repetitive process on @math . At time step @math the vertices of @math are colored black and the other vertices are colored white. After that, at each time step @math , the colors of white vertices (if any) are updated according to the following rule. All white vertices @math that have at least @math black neighbors at the time step @math are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called Target Set Selection: Find a target set @math of smallest possible size such that all vertices in @math are black at the end of the process. Such an @math is called an optimal target set for @math under the th... Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model. Given a set @math with @math elements and a family @math of subsets, we show how to partition @math into @math such subsets in @math time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in @math time for several well-studied partition problems including domatic number, chromatic number, maximum @math -cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time @math if membership in @math can be decided in polynomial time. We solve chromatic number in @math time and domatic number in @math time. Finally, we present a family of polynomial space approximation algorithms that find a number between @math and @math in time @math . The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be @math and @math . When graph Ramsey theory is viewed as a game, "Painter" 2-colors the edges of a graph presented by "Builder". Builder wins if every coloring has a monochromatic copy of a fixed graph @math . In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class @math . Builder wins the game @math if a monochromatic copy of @math can be forced. The on-line degree Ramsey number @math is the least @math such that Builder wins @math when @math is the class of graphs with maximum degree at most @math . Our results include: 1) @math if and only if @math is a linear forest or each component lies inside @math . 2) @math , where @math . 3) @math for a tree @math , where @math and @math are two largest vertex degrees. 4) @math , with @math except for finitely many odd values of @math . 5) @math when @math . The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays "consistently". Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p @math c n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p @math polylog(n) n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c. Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least @math rounds, otherwise the probability that all processors are colored legally is less than @math . A similar time bound holds for selecting a maximal independent set. The bound is tight (up to a constant factor) in light of the deterministic algorithms of Cole and Vishkin [Inform, and Control, 70 (1986), pp. 32–53] and extends the lower bound for deterministic algorithms of Linial [Proc. 28th IEEE Foundations of Computer Science Symposium, 1987, pp. 331–335]. We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices @math . We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity @math , where @math is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error @math for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to @math and @math . Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least @math queries. In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials @math and show that if @math and there is a disk @math centered at zero in the complex plane such that @math does not vanish on @math for all bounded degree graphs @math , then for each @math in the interior of @math there exists a deterministic polynomial-time approximation algorithm for evaluating @math at @math . This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated b... We present a simple distributed @math -approximation algorithm for maximum weight independent set (MaxIS) in the @math model which completes in @math rounds, where @math is the maximum degree, @math is the number of rounds needed to compute a maximal independent set (MIS) on @math , and @math is the maximum weight of a node. Whether our algorithm is randomized or deterministic depends on the MIS algorithm used as a black-box. Plugging in the best known algorithm for MIS gives a randomized solution in @math rounds, where @math is the number of nodes. We also present a deterministic @math -round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a @math -approximation for maximum weight matching without incurring any additional round penalty in the @math model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of for which we describe a mechanism that allows the simulation to run in the @math model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to ( @math ) allows us to devise a distributed algorithm requiring @math rounds for any constant @math . For the unweighted case, we can even obtain a @math -approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on @math . We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all @math . This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of @math -colorings of a @math -regular graph, for any @math , is maximized by a union of @math 's. This proves the @math case of a conjecture of Galvin and Tet ali. By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in @math O(Δ) rounds, independently of @math n; here @math Δ is the maximum degree of the graph and @math n is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in @math o(Δ) rounds, independently of @math n. Our work gives the first linear-in- @math Δ lower bound for a natural graph problem in the standard @math LOCAL model of distributed computing--prior lower bounds for a wide range of graph problems have been at best logarithmic in @math Δ. We study a one-parameter family of discrete dynamical systems called the @math -color firefly cellular automata (FCAs), which were introduced recently by the author. At each discrete time @math , each vertex in a graph has a state in @math , and a special state @math is designated as the blinking' state. At step @math , simultaneously for all vertices, the state of a vertex increments from @math to @math unless @math and at least one of its neighbors is in the state @math . A central question about this system is that on what class of network topologies synchrony is guaranteed to emerge. In a previous work, we have shown that for @math , every @math -coloring on a finite tree synchronizes iff the maximum degree is less than @math , and asked whether this behavior holds for all @math . In this paper, we answer the question positively for @math and negatively for all @math by constructing counterexamples on trees with maximum degree at most @math . Given a set of @math n points, each is painted by one of the @math k given colors, we want to choose @math k points with distinct colors to form a color spanning set. For each color spanning set, we can construct the convex hull and the smallest axis-aligned enclosing rectangle, etc. Assuming that each point is chosen independently and identically from the subset of points of the same color, we propose an @math O ( n 2 ) time algorithm to compute the expected area of convex hulls of the color spanning sets and an @math O ( n 2 ) time algorithm to compute the expected perimeter of convex hulls of the color spanning sets. For the expected perimeter (resp. area) of the smallest perimeter (resp. area) axis-aligned enclosing rectangles of the color spanning sets, we present an @math O ( n log n ) (resp. @math O ( n 2 ) ) time algorithm. We also propose a simple approximation algorithm to compute the expected diameter of the color spanning sets. For the expected distance of the closest pair, we show that it is @math # P-complete to compute and there exists no polynomial time @math 2 n 1 - ? approximation algorithm to compute the probability that the closest pair distance of all color spanning sets equals to a given value @math d unless @math P = N P , even in one dimension and when each color paints two points.