The input to a PPNC instance is integers n and p, and a non-negative real weighting of the edges of the clique Kn on the vertex set {1,..., n}. We are asked to find a set of p disjoint cycles spanning {1,..., n} and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p. For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T-join With Slack problem. The input to an instance of Mod k T-join with Slack consists of integers n and B, a non-negative weighting of the edges of the clique Kn, and a label l(v) from {0,1,..., k - 1} on each vertex of Kn. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑T∈F((∑v∈V(T)l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T-join problem which can be solved exactly in polynomial time.

We show Maker wins the Maker-Breaker perfect matching game in n/2 + o(n) turns when the bias is at least n/ln n − f(n)n/(ln n)5/4, for any f going to infinity with n and n sufficiently large (in terms of f).

We show that there is a constant C such that for any b < n/ln n − Cn/(ln n)3/2, Maker can win the Maker-Breaker Hamilton cycle game in n + Cn/√ln n steps.

A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ( \(n\rightarrow \infty \) ). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.

We consider decomposing a 3-connected planar graph G using laminar separators of size three. We show how to find a maximal set of laminar 3-separators in such a graph in linear time. We also discuss how to find maximal laminar set of 3-separators from special families. For example we discuss non-trivial cuts, ie. cuts which split G into two components of size at least two. For any vertex v, we also show how to find a maximal set of 3-separators disjoint from v which are laminar and satisfy: every vertex in a separator X has two neighbours not in the unique component of G – X containing v. In all cases, we show how to construct a corresponding tree decomposition of adhesion three. Our new algorithms form an important component of recent methods for finding disjoint paths in nonplanar graphs.

The traditional Erdos-Renyi model of a random network is of little use in modelling the type of complex networks which modern researchers study. In this graph, every pair of vertices is equally likely to be connected by an edge. However, 21st century networks are of diverse nature and usually exhibit inhomogeneity among their nodes. This motivates the study, for a fixed degree sequence D=(d1, ..., dn), of a uniformly chosen simple graph G(D) on {1, ..., n} where the vertex i has degree di. In this paper, we study the existence of a giant component in G(D). A heuristic argument suggests that a giant component in G(D) will exist provided that the sum of the squares of the degrees is larger than twice the sum of the degrees. In 1995, Molloy and Reed essentially proved this to be the case when the degree sequence D under consideration satisfies certain technical conditions [Random Structures & Algorithms, 6:161-180]. This work has attracted considerable attention, has been extended to degree sequences under weaker conditions and has been applied to random models of a wide range of complex networks such as the World Wide Web or biological systems operating at a sub-molecular level. Nevertheless, the technical conditions on D restrict the applicability of the result to sequences where the vertices of high degree play no important role. This is a major problem since it is observed in many real-world networks, such as scale-free networks, that vertices of high degree (the so-called hubs) are present and play a crucial role. In this paper we characterize when a uniformly random graph with a fixed degree sequence has a giant component. Our main result holds for every degree sequence of length n provided that a minor technical condition is satisfied. The typical structure of G(D) when D does not satisfy this condition is relatively simple and easy to understand. Our result gives a unified criterion that implies all the known results on the existence of a giant component in G(D), including both the generalizations of the Molloy-Reed result and results on more restrictive models. Moreover, it turns out that the heuristic argument used in all the previous works on the topic, does not extend to general degree sequences.

Ramsey's theorem says that for every clique $H_1$ and for every graph $H_2$ with no edges, all graphs containing neither of $H_1,H_2$ as induced subgraphs have bounded order. What if, instead, we exclude a graph $H_1$ with a vertex whose deletion gives a clique, and the complement $H_2$ of another such graph? This no longer implies bounded order, but it implies tightly restricted structure that we describe. There are also several related subproblems (what if we exclude a star and the complement of a star? what if we exclude a star and a clique? and so on) and we answer a selection of these.

A key result of Robertson and Seymour's graph minor theory is a structure theorem stating that all graphs excluding some fixed graph as a minor have a tree decomposition into pieces that are almost embeddable in a fixed surface. Most algorithmic applications of graph minor theory rely on an algorithmic version of this result. However, the known algorithms for computing such graph minor decompositions heavily rely on the very long and complicated proofs of the existence of such decompositions, essentially they retrace these proofs and show that all steps are algorithmic. In this paper, we give a simple quadratic time algorithm for computing graph minor decompositions. The best previously known algorithm due to Kawarabayashi and Wollan runs in cubic time and is far more complicated. Our algorithm combines techniques from logic and structural graph theory, or more precisely, a variant of Courcelle's Theorem stating that monadic second-order logic formulas can be evaluated in linear time on graphs of bounded tree width and Robertson and Seymour's so called Weak Structure Theorem.

Let $g(t)$ be the minimum number such that every graph $G$ with average degree $d(G) \geq g(t)$ contains a $K_{t}$-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that $g(t) \in \Theta(t\sqrt{\log t})$. This paper shows that for all fixed $\epsilon > 0$ and fixed sufficiently large $t \geq t(\epsilon)$, if $d(G) \geq (2+\epsilon)g(t)$, then we can find this $K_{t}$-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when $d(G) \geq 2^{t-2}$.

Let $D$ be a digraph. The chromatic number $\chi(D)$ of $D$ is the smallest number of colors needed to color the vertices of $D$ such that every color class induces an acyclic subdigraph. The girth of $D$ is the length of a shortest directed cycle, or $\infty$ if $D$ is acyclic. Let $G(k,n)$ be the maximum possible girth of a digraph on $n$ vertices with $\chi(D) > k$. It is shown that $G(k,n) \ge \left\lfloor n^{1/k}\right\rfloor$ and $G(k,n) \le (3\log_2 n \log_2\log_2 n)^{1-1/k} n^{1/k}$ for $n \ge 3$ and $k \ge 2$.

An $L(p,1)$-labeling of a graph is a function f from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices x and y in the graph. The span of an $L(p,1)$-labeling f is the difference between the largest and the smallest labels used by f. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$. We settle this conjecture for $\Delta$ sufficiently large. More generally, we show that for any positive integer p there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$. This yields that for each positive integer p, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labeling with span at most $\Delta^2+C_p$.

We generalize the seminal Graph Minor algorithm of Robertson and Seymour to the parity version. We give polynomial time algorithms for the following problems: 1) the parity H-minor (Odd Kk-minor) containment problem, and 2) the disjoint paths problem with k terminals and the parity condition for each path, as well as several other related problems. We present an O(ma(m, n)n) time algorithm for these problems for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function a(m,n) is the inverse of the Ackermann function (see Tarjan [69]). Note that the first problem includes the problem of testing whether or not a given graph contains k disjoint odd cycles (which was recently solved in [24], [34]), if we fix H to be equal to the graph of k disjoint triangles. The algorithm for the second problem generalizes the Robertson Seymour algorithm for the k-disjoint paths problem. As with the Robertson-Seymour algorithm for the k-disjoint paths problem for any fixed k, in each iteration, we would like to either use the presence of a huge clique minor, or alternatively exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an "odd clique minor". This requires new techniques to describe the structure of the graph when we cannot find such a minor. We emphasize that our proof for the correctness of the above algorithms does not depend on the full power of the Graph Minor structure theorem [56]. Although the original Graph Minor algorithm of Robertson and Seymour does depend on it and our proof does have similarities to their arguments, we can avoid the structure theorem by building on the shorter proof for the correctness of the graph minor algorithm in [35]. This work was done as a part of an INRIA-NII collaboration under MOU grant, and partially supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas "New Horizons in Computing" Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, by C & C Foundation, by Kayamori Foundation and by Inoue Research Award for Young Scientists. Consequently, we are able to avoid the much of the heavy machinery of the Graph Minor structure theory. Utilizing some results of [35] and [62], [63], our proof is less than 50 pages.

The term Probabilistic Method refers to the proof of deterministic statements using probabilistic tools. The method has been successfully applied to a number of problems in the field of graph colouring. We survey some of the results thereby obtained. The talk is intended to be accessible and short on details. We will first define graph colouring, explain the type of graph colouring problems which tend to attract interest. We then explain the probabilistic tools which are used to solve them, and why we would expect the type of tools that are used to be effective for solving the types of problems typically studied.

It is shown that for each t, there is a separator of size O(t√n) in any n-vertex graph G with no Kt-minor. This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc, 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with n vertices and genus g has a separator of order O(√gn), because Kthas genus Ω(t2). The bound O(t√n) is best possible because every 3-regular expander graph with n vertices is a graph with no Kt-minor for t = cn1/2, and with no separator of size dn for appropriately chosen positive constants c, d. In addition, we give an O(n2) time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in O(n1+ε) time for any ε > 0. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order g(t)√n, for some function g of t, in an n-vertex graph G with no Kt-minor in O(n) time.

A totally odd K4-subdivision is a subdivision of K4 where each subdivided edge has odd length. The recognition of a totally odd K4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter [53], Zang [63] and Thomassen [60] independently conjectured the existence of a polynomial time recognition algorithm. In this paper, we give the first polynomial time algorithm for solving this problem. We also study the the parity two disjoint rooted paths problem where we determine if there exists two vertex disjoint paths of a specified parity between two pairs of terminals. Using a similar technique, we give an O(|E(G)||V(G)|α(|E(G)|,|V(G)|)) algorithm for the parity two disjoint rooted paths problem on an input graph G, where α(|E(G)|,|V(G)|) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the well-known non-parity version of the two disjoint rooted paths problem [19, 50, 52, 55, 58]. We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the non-parity version of the algorithm in [22]. Thomassen [61] gave a polynomial algorithm for the case k = 2 and hoped to use this algorithm to recognize a totally odd K4-subdivision. Our algorithm runs in O(|E(G)||V(G)|α(|E(G)|, |V(G)|)) for any fixed k. Finally, we give an O(|V(G)|2 + |E(G)|α(|E(G)|,|V(G)|log|V(G)|)) algorithm to decide whether a graph contains k disjoint paths from A to B (with |A| = |B| = k) that are not all of the same parity. This answers a conjecture of Thomassen [60]. This problem arises from the study of totally odd-K4-subdivisions in 3-connected graphs [60].

We consider the following problem, which is called the odd cycles transversal problem. Input: A graph G and an integer k. Output: A vertex set X ∊ V(G) with |X| ≤ k such that G – X is bipartite. We present an O(mα(m, n)) time algorithm for this problem for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function α(m, n) is the inverse of the Ackermann function (see by Tarjan [38]). This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(nm) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i.e, there is an edge set X′ ∊ E(G) such that G – X′ is bipartite. Using this algorithm and the recent result in [16], we give an O(mα(m, n) + n log n) algorithm for the following problem for any fixed k: Input: A graph G and an integer k. Output: Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C1, …, Ck in G such that each vertex is on at most two of these odd cycles. This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(n3) time algorithm for this problem. We also give a much simpler and much shorter proof for the following result by Reed [28]. The Erdős-Pósa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f(k) such that G – X is bipartite for some function f of k. Note that the Erdős-Pósa property does not hold for odd cycles in general.

We consider the following problem, which is called the odd cycle packing problem. Input: A graph $G$ with n vertices and m edges, and an integer k. Output: k vertex disjoint odd cycles. We also consider the edge disjoint case, and the node- and arc-disjoint directed case. This problem is known to be NP-hard, even for planar graphs, if k is part of input. In this paper, we first present the integrality gap and hardness results for these problems. We prove that the integrality gap of the standard LP-relaxation of the odd cycle packing problem is Θ (√n). This result is obtained by giving an algorithm to compute an odd cycle packing, which gives rise to an O(√n) approximating algorithm for the fractional odd cycle packing problem (this gives rise to an upper bound), and by showing that there is a graph G such that there is an O(√n) half-integral odd cycle packing in G, but there are no two disjoint odd cycle in G (this gives rise to a lower bound). For the hardness result, we prove that for any ε, the node-disjoint directed odd cycle packing problem is NP-hard to approximate within m1/2-ε, where m is the number of arcs of a given digraph G. This is true not only for the node-disjoint directed odd cycle packing problem but also for the arc-disjoint directed odd cycle packing problem. In addition, we prove that there is an O(m1/2)-approximation algorithm for the node- and arc- directed odd cycle packing problems. Thus this approximation algorithm almost matches the hardness result. For the positive side, we consider the case when the number of odd cycles, k, is fixed. This is a natural direction, for example, the seminal result of Robertson and Seymour for the disjoint paths problem in the graph minors project. We present an O(m α(m,n) n) algorithm for any fixed k, where the function α(m,n) is the inverse of the Ackermann function (see by Tarjan [72]). This is the first polynomial time algorithm for this problem (and in fact, it is the first fixed parameter tractable algorithm). This proves a conjecture by Lovasz and Schrijver in early 1980's, who gave a polynomial time algorithm for the case k=2. Our algorithm can be applied to decide whether or not G has k edge disjoint odd cycle with the same time complexity for any fixed k. We also show that our algorithm gives rise to the Graph Minor Algorithm for the k vertex-disjoint paths problem by Robertson and Seymour for any fixed k. Thus our algorithm is beyond the framework of the Graph Minor Theory. Our algorithm has several appealing features: We use the odd S-path theorem, which is a generalization of the well-known S-paths theorem by Mader. We also introduce an odd clique minor, which can be viewed as a clique minor with some parity condition. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem for any fixed k, in each iteration, we would like to either use a huge clique minor as a "crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the cycles and can only use an "odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. This part needs the seminal result of Robertson and Seymour for the graph minor decomposition theorem for H-minor-free graphs. We also use some deep results of Robertson and Seymour that are needed to prove the correctness of their algorithm for the disjoint paths problem.

We consider the following problem, which is called the half integral parity disjoint paths packing problem. Input: A graph G, k pair of vertices (s1, t1), (s2, t2), …, (sk, tk) in G (which are sometimes called terminals), and a parity li for each i with 1 ≤ i ≤ k, where li = 0 or 1. Output : Paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k and parity of length of the path Pi is li, i.e, if li = 0, then length of Pi is even, and if li = 1, then length of Pi is odd for i = 1, 2, …, k. In addition, each vertex is on at most two of these paths. We present an O(mα(m, n) log n) algorithm for fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function α(m, n) is the inverse of the Ackermann function (see by Tarjan [43]). This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg [23] and Kawarabayashi and Reed [20], respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a “crossbar”, or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an “odd clique minor”. We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. We also have algorithms running in O(m(1+∊)) time for any ∊ > 0 for this problem, if k is up to o(log log log n) for general graphs, up to o(log log n) for planar graphs, and up to o(log log n/g) for graphs on the surface, where g is Euler genus. Furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case.

We prove that every graph with maximum degree Δ can be properly (Δ + 1)-coloured so that no colour appears more than O(logΔ/log logΔ) times in the neighbourhood of any vertex. This is best possible up to the constant factor in the O(–) term. We also provide an efficient algorithm to produce such a colouring.

The famous Hadwiger's conjecture asserts that every graph with no Kt-minor is (t-1)-colorable. The case t=5 is known to be equivalent to the Four Color Theorem by Wagner, and the case t=6 is settled by Robertson, Seymour and Thomas. So far the cases t ≥ 7 are wide open. In this paper, we prove the following two theorems: There is an O(n2) algorithm to decide whether or not a given graph G satisfies Hadwiger's conjecture for the case t. Every minimal counterexample to Hadwiger's conjecture for the case t has at most f(t) vertices for some explicit bound f(t). The bound f(t) is at most pppt, where p=101010t. Our proofs for both results use the well-known result by Thomassen [46] for 5-list-coloring planar graphs, together with some results (but not the decomposition theorem) of Graph Minors in [36]. Concerning the first result, we prove the following stronger theorem: For a given graph G and any fixed t, there is an O(n2) algorithm to output one of the following: a (t-1)-coloring of G, or a Kt-minor of G, or a minor H of G of order at most f(t) such that H does not have a Kt-minor nor is (t-1)-colorable. The last conclusion implies that H is a counterexample to Hadwiger's conjecture with at most f(t) vertices for the case t. The time complexity of the algorithm matches the best known algorithms for 4-coloring planar graphs (the Four Color Theorem), due to Appel and Hakken, and Robertson, Sanders, Seymour and Thomas, respectively. Let us observe that when t=5, the algorithm gives rise to an algorithm for the Four Color Theorem. The second theorem follows from our structure theorem, which has the following corollary: Every minimal counterexample G to Hadwiger's conjecture for the case t either has at most f(t) vertices, or has a vertex set Z of order at most t-5 such that G-Z is planar. It follows from the Four Color Theorem that the second assertion does not happen to any minimal counterexample to Hadwiger's conjecture for the case t. Thus in constant time, we can decide Hadwiger's conjecture for the case t.

Let G be an n -vertex m -edge graph with weighted vertices. A pair of vertex sets A , B ⊆ V ( G ) is a 2/3 -separation of order | A ∩ B | if A ∪ B = V ( G ), there is no edge between A − B and B − A , and both A − B and B − A have weight at most 2/3 the total weight of G . Let ℓ ∈ Z + be fixed. Alon et al. [1990] presented an algorithm that in O ( n 1/2 m ) time, outputs either a K ℓ -minor of G , or a separation of G of order O ( n 1/2 ). Whether there is a O ( n + m )-time algorithm for this theorem was left as an open problem. In this article, we obtain a O ( n + m )-time algorithm at the expense of a O ( n 2/3 ) separator. Moreover, our algorithm exhibits a trade-off between time complexity and the order of the separator. In particular, for any given ϵ ∈ [0,1/2], our algorithm outputs either a K ℓ -minor of G , or a separation of G with order O ( n (2−ϵ)/3 in O ( n 1 + ϵ + m ) time. As an application we give a fast approximation algorithm for finding an independent set in a graph with no K ℓ-minor.

For every fixed surface S, orientable or non-orientable, and a given graph G, Mohar (STOC'96 and Siam J. Discrete Math. (1999)) described a linear time algorithm which yields either an embedding of G in S or a minor of G which is not embeddable in S and is minimal with this property. That algorithm, however, needs a lot of lemmas which spanned six additional papers. In this paper, we give a new linear time algorithm for the same problem. The advantages of our algorithm are the following: 1. The proof is considerably simpler: it needs only about 10 pages, and some results (with rather accessible proofs) from graph minors theory, while Mohar's original algorithm and its proof occupy more than 100 pages in total. 2. The hidden constant (depending on the genus g of the surface S) is much smaller. It is singly exponential in g, while it is doubly exponential in Mohar's algorithm. As a spinoff of our main result, we give another linear time algorithm, which is of independent interest. This algorithm computes the genus and constructs minimum genus embeddings of graphs of bounded tree-width. This resolves a conjecture by Neil Robertson and solves one of the most annoying long standing open question about complexity of algorithms on graphs of bounded tree-width.

A graph G is strict quasi parity (SQP) if every induced subgraph of G that is not a clique contains a pair of vertices with no odd chordless path between them (an even pair). Hougardy conjectured that the minimal forbidden subgraphs for the class of SQP graphs are the odd chordless cycles, the complements of odd or even chordless cycles, and some line-graphs of bipartite graphs. Here we prove this conjecture for planar graphs. We also give a constructive characterization of all the planar minimal forbidden subgraphs for the class of SQP graphs.

We show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has crossing number at most k, and if this is the case, computes a drawing of the graph in the plane with at most k crossings. This answers the question posed by Grohe (STOC'01 and JCSS 2004). Our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan lin1, which determines if a given graph is planar in linear time.

Let ${\cal F}$ be a family of graphs. Two graphs G 1 = (V 1 ,E 1 ), G 2 =(V 2 ,E 2 ) are said to have the same ${\cal F}$-structure if there is a bijection $f: V_1 \rightarrow V_2$ such that a subset S induces a graph belonging to ${\cal F}$ in G 1 if and only if its image f(S) induces a graph belonging to ${\cal F}$ in G 2 . We characterize those graphs which have the same $\{P_3,\overline{P}_3\}$-structure, or the same $\{K_3,\overline{K}_3\}$-structure. This characterization shows that graph H is perfect if and only if it has the $\{P_3,\overline{P}_3\}$-structure of some perfect graph G. In proving the main result, we need and prove the following result, which is of independent interest: If a graph J is claw-free and co-claw-free, then either (i) J has at most nine vertices, or (ii) every component of J is a path or a hole, or (iii) every component of $\overline{J}$ is a path or a hole.

LetHnbe the height of a random binary search tree onnnodes. We show that there exist constants α = 4.311… and β = 1.953… such thatE(Hn) = αln n− βln ln n+O(1), We also show thatVar(Hn) =O(1).

We consider for graphs of maximum degree Δ, the problem of determining whether χG) > Δ-k for various values of k. We obtain sharp theorems characterizing when the barrier to Δ-k colourability must be a local condition, i.e. a small subgraph, and when it can be global. We also show that for large fixed Δ, this problem is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case prove that Hitting Set with sets of size B is hard to approximate to within a factor $B^{1/19}$. The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B=2. The relationship between hardness of approximation and set size seems to have not been explored before.

Article How tall is a tree? Share on Author: Bruce Reed CNRS, Paris, France CNRS, Paris, FranceView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 479–483https://doi.org/10.1145/335305.335360Published:01 May 2000 2citation473DownloadsMetricsTotal Citations2Total Downloads473Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In cellular telephone networks, sets of radio channels (colors) must be assigned to transmitters (vertices) while avoiding interference. Often, the transmitters are laid out like vertices of a triangular lattice in the plane. We investigated the corresponding weighted coloring problem of assigning sets of colors to vertices of the triangular lattice so that the sets of colors assigned to adjacent vertices are disjoint. We present a hardness result and an efficient algorithm yielding an approximate solution. © 2000 John Wiley & Sons, Inc.

Copyright © 1998 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or [email protected]. © ACM, 1998. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing (1998). http://doi.acm.org/10.1145/276698.276866

We provide a polynomial time algorithm which finds a total coloring of any graph with maximum degree $\D$, $\D$ sufficiently large, using at most $\D+8\log^8\D$ colors. This improves the best previous upper bound on the total chromatic number of $\D+18\D^{1/3}\log(3\D)$.

Let $H_{n}$ be the height of a random binary search tree on n nodes. We show that there exists a constant $\alpha = 4.31107 \ldots $ such that ${\textbf P} \{|H_{n} - \alpha \log n| > \beta \log \log n\} \rightarrow 0 $, where $\beta > 15 \alpha/\ln 2 = 93.2933 \ldots $. The proof uses the second moment method and does not rely on properties of branching processes. We also show that $\operatorname{Var}\{H_{n}\} = O((\log\log n)^{2})$.

We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem $\textit{ATSP}(M)$ and the value of its assignment relaxation $\textit{AP}(M)$. We assume here that the costs are given by an $n \times n$ matrix M whose entries are independently and identically distributed. We focus on the relationship between $Pr(\textit{ATSP}(M) = \textit{AP}(M))$ and the probability $p_{n}$ that any particular entry is zero. If $np_{n} \rightarrow \infty $ with n then we prove that $\textit{ATSP}(M) = \textit{AP}(M)$ with probability 1-o(1). This is shown to be best possible in the sense that if $np (n) \rightarrow c,\, c > 0$ and constant, then $Pr(\textit{ATSP}(M) = \textit{AP}(M)) < 1 - \phi (c)$ for some positive function $\phi$. Finally, if $np_{n} \rightarrow 0$ then $Pr(\textit{ATSP}(M) = \textit{AP}(M)) \rightarrow 0$.

Consider a randomly generated boolean formula F (in the conjunctive normal form) with m clauses of size k over n variables; k is fixed at any value greater than 1, but n tends to infinity and m = (1 + o(1))cn for some c depending only on k. It is easy to see that F is unsatisfiable with probability 1-o(1) whenever c>(ln 2)2/sup k/; the authors complement this observation by proving that F is satisfiable with probability 1-o(1) whenever c1.>

We show that for any fixed k, there is a linear-time algorithm which given a graph G either: (i) finds a cutset X of G with |X| ≤ k such that no component of G–X contains more than 3/4|G–X| vertices, or (ii) determines that for any set X of vertices of G with |X| ≤ k, there is a component of G–X which contains more than 2/3|G–X| vertices.

The problem of finding a perfect matching of small total length in a complete graph whose vertices are points in the interval [0,1] is considered. The greedy heuristic for this problem repeatedly picks the two closest unmatched points x and y, and adds the edge $xy$ to the matching. It is shown that if $2n$ points are randomly chosen uniformly in $[0,1]$, then the expected length of the matching given by the greedy algorithm is $\theta (\log n)$. This compares unfavourably with the length of the shortest perfect matching, which is always less than 1.