Fast 3-coloring Triangle-Free Planar Graphs

Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(nlogn)\mathcal{O}(n\log n) .     

Efficient Algorithms for k-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Efficient Algorithms for <Emphasis Type="Italic">k</Emphasis>-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Order-k voronoi diagrams of sites with additive weights in the plane

It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k?2)(n?k) vertices, (6k?3)(n?k) edges, and (2k?1)(n?itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k ² n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.     

Randomized parallel list ranking for distributed memory multiprocessors

We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP type model. We first describe a simple version which requires, with high probability, log(3p)+log ln(n)=Õ(logp+log logn) communication rounds (h-relations withh=Õ(n/p)) andÕ(n/p)) local computation. We then outline an improved version that requires high probability, onlyr?(4k+6) log(2/3p)+8=Õ(k logp) communication rounds wherek=min{i?0 |ln(i+1)n?(2/3p)²ⁱ⁺¹}. Notekn) is an extremely small number. Forn andp?4, the value ofk is at most 2. Hence, for a given number of processors,p, the number of communication rounds required is, for all practical purposes, independent ofn. Forn?1, 500,000 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 78, but the actual number of communication rounds observed so far is 25 in the worst case. Forn?10010100 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118; and we conjecture that the actual number of communication rounds required will not exceed 50. Our algorithm has a considerably smaller member of communication rounds than the list ranking algorithm used in Reid-Miller’s empirical study of parallel list ranking on the Cray C-90.⁽¹⁾ To our knowledge, Reid-Miller’s algorithm⁽¹⁾ was the fastest list ranking implementation so far. Therefore, we expect that our result will have considerable practical relevance.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Ein Algorithmus zur Ermittlungk-bester Kantenfolgen zwischen allen Ecken eines Graphen

This paper describes a new matrix-algorithm for determining all shortest up tok-shortest distances between then vertices of a network. The outstanding property of this algorithm consists in the necessary amount of additions/subtractions which can be estimated, forn?k, not to exceed 1/3n ^5/2 k ^5/2+5n ^5/2 k ^3/2+0(n ^3/2 k ^5/2) whereas the number of comparisons lies, as in other algorithms, in the range ofn ³ k ³. This paper also includes a formal proof of the validity of the algorithm and a short comparison with different, known methods.     

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions

We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an  $O(2^{6.903\sqrt{n}})We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an  O(2^6.903?n)O(2^{6.903\sqrt{n}}) time algorithm solving weighted Hamiltonian Cycle on an n-vertex planar graph. Similar technique solves Planar Graph Travelling Salesman Problem with n cities in time O(2^9.8594?n)O(2^{9.8594\sqrt{n}}) . Our approach can be used to design parameterized algorithms as well. For example, we give an algorithm that for a given k decides if a planar graph on n vertices has a cycle of length at least k in time O(2^13.6?kn+n³)O(2^{13.6\sqrt{k}}n+n^{3}) .     

On induced-universal graphs for the class of bounded-degree graphs

For a family F of graphs, a graph U is said to be F-induced-universal if every graph of F is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most k. For k even, our induced-universal graph has O(nk/2) vertices and for k odd it has O(n⌈k/2⌉−1/klog2+2/kn) vertices. This construction improves a result of Butler by a multiplicative constant factor for the even case and by almost a multiplicative n1/k factor for the odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result of Butler.     

Zur Konvergenz der Ableitungen von Interpolationspolynomen

Letp _n denote the polynomial of degreen or less that interpolates a given smooth functionf at the ?eby?ev nodest _j ⁿ =cos(jπ/n), 0≤j≤n, and let ‖·‖ be the maximum norm inC[?1, 1]. It is proved that fork-th derivatives (2≤k≤n) estimates of the following type hold $$\parallel f^{(k)} - p_n^{(k)} \parallel \leqslant c_k n^{k - 1} \inf \{ \parallel f^{(k)} - q\parallel :q \in \Pi _{n - k} \} .$$ In this relationc _k only depends onk andΠ _n?k denotes the space of polynomials up to degreen?k.     

An optimal bit complexity randomized distributed MIS algorithm

We present a randomized distributed maximal independent set (MIS) algorithm for arbitrary graphs of size n that halts in time O(log n) with probability 1 ? o(n ^?1), and only needs messages containing 1 bit. Thus, its bit complexity par channel is O(log n). We assume that the graph is anonymous: unique identities are not available to distinguish between the processes; we only assume that each vertex distinguishes between its neighbours by locally known channel names. Furthermore we do not assume that the size (or an upper bound on the size) of the graph is known. This algorithm is optimal (modulo a multiplicative constant) for the bit complexity and improves the best previous randomized distributed MIS algorithms (deduced from the randomized PRAM algorithm due to Luby (SIAM J. Comput. 15:1036?C1053, 1986)) for general graphs which is O(log² n) per channel (it halts in time O(log n) and the size of each message is log n). This result is based on a powerful and general technique for converting unrealistic exchanges of messages containing real numbers drawn at random on each vertex of a network into exchanges of bits. Then we consider a natural question: what is the impact of a vertex inclusion in the MIS on distant vertices? We prove that this impact vanishes rapidly as the distance grows for bounded-degree vertices and we provide a counter-example that shows this result does not hold in general. We prove also that these results remain valid for Luby??s algorithm presented by Lynch (Distributed algorithms. Morgan Kaufman 1996) and by Wattenhofer (http://dcg.ethz.ch/lectures/fs08/distcomp/lecture/chapter4.pdf, 2007). This question remains open for the variant given by Peleg (Distributed computing??a locality-sensitive approach 2000).     

Succinct Representation of Labeled Graphs

In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider planar triangulations, planar graphs and k-page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main contribution. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counter clockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a k-page graph when k is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in O(lg?k) time, while previous work uses O(k) time.     

Unconditional lower bounds for learning intersections of halfspaces

We prove new lower bounds for learning intersections of halfspaces, one of the most important concept classes in computational learning theory. Our main result is that any statistical-query algorithm for learning the intersection of $\sqrt{n}$ halfspaces in n dimensions must make $2^{\varOmega (\sqrt{n})}$ queries. This is the first non-trivial lower bound on the statistical query dimension for this concept class (the previous best lower bound was n ^Ω(log?n)). Our lower bound holds even for intersections of low-weight halfspaces. In the latter case, it is nearly tight. We also show that the intersection of two majorities (low-weight halfspaces) cannot be computed by a polynomial threshold function (PTF) with fewer than n ^{Ω(log?n/log?log?n)} monomials. This is the first super-polynomial lower bound on the PTF length of this concept class, and is nearly optimal. For intersections of k=ω(log?n) low-weight halfspaces, we improve our lower bound to $\min\{2^{\varOmega (\sqrt{n})},n^{\varOmega (k/\log k)}\},$ which too is nearly optimal. As a consequence, intersections of even two halfspaces are not computable by polynomial-weight PTFs, the most expressive class of functions known to be efficiently learnable via Jackson’s Harmonic Sieve algorithm. Finally, we report our progress on the weak learnability of intersections of halfspaces under the uniform distribution.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Improved FPT algorithm for feedback vertex set problem in bipartite tournament

We present an O(k³n²+n³) time FPT algorithm for the feedback vertex set problem in a bipartite tournament on n vertices with integral weights. This improves the previously best known O(k^3.12n⁴) time FPT algorithm for the problem.     

On the geodesic voronoi diagram of point sites in a simple polygon

Given a simple polygon withn sides in the plane and a set ofk point “sites” in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal “geodesic” distance inside the polygon as the metric. We describe anO((n + k) log(n + k) logn)-time algorithm for solving this problem and sketch a fasterO((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.     

On Reversible Cascades in Scale-Free and Erdős-Rényi Random Graphs

Consider the following cascading process on a simple undirected graph G(V,E) with diameter Δ. In round zero, a set S?V of vertices, called the seeds, are active. In round i+1, i∈?, a non-isolated vertex is activated if at least a ρ∈(0,1] fraction of its neighbors are active in round i; it is deactivated otherwise. For k∈?, let min-seed^(k)(G,ρ) be the minimum number of seeds needed to activate all vertices in or before round k. This paper derives upper bounds on min-seed^(k)(G,ρ). In particular, if G is connected and there exist constants C>0 and γ>2 such that the fraction of degree-k vertices in G is at most C/k ^γ for all k∈?⁺, then min-seed^(Δ)(G,ρ)=O(?ρ ^γ?1|V|?). Furthermore, for n∈?⁺, p=Ω((ln(e/ρ))/(ρn)) and with probability 1?exp(?n ^Ω(1)) over the Erd?s-Rényi random graphs G(n,p), min-seed⁽¹⁾(G(n,p),ρ)=O(ρn).     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.