Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

We present a generic scheme for approximating NP-hard problems on graphs of treewidth k=ω(logn). When a tree-decomposition of width ? is given, the scheme typically yields an ?/logn-approximation factor; otherwise, an extra logk factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

Acyclic and k-distance coloring of the grid

In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n₁,n₂,…,n_d) (with n_i vertices in each dimension 1?i?d), for two different types of vertex colorings: (1) acyclic coloring of graphs, in which we color the vertices such that (i) no two neighbors are assigned the same color and (ii) for any two colors i and j, the subgraph induced by the vertices colored i or j is acyclic; and (2) k-distance coloring of graphs, in which every vertex must be colored in such a way that two vertices lying at distance less than or equal to k must be assigned different colors. The minimum number of colors needed to acyclically color (respectively k-distance color) a graph G is called acyclic chromatic number of G (respectively k-distance chromatic number), and denoted a(G) (respectively χ_k(G)).The method we propose for coloring the d-dimensional grid in those two variants relies on the representation of the vertices of G_d(n₁,…,n_d) thanks to its coordinates in each dimension; this gives us upper bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)).We also give lower bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)). In particular, we give a lower bound on a(G) for any graph G; surprisingly, as far as we know this result was never mentioned before. Applied to the d-dimensional grid G_d(n₁,…,n_d), the lower and upper bounds for a(G_d(n₁,…,n_d)) match (and thus give an optimal result) when the lengths in each dimension are “sufficiently large” (more precisely, if ). If this is not the case, then these bounds differ by an additive constant at most equal to . Concerning χ_k(G_d(n₁,…,n_d)), we give exact results on its value for (1) k=2 and any d?1, and (2) d=2 and any k?1.In the case of acyclic coloring, we also apply our results to hypercubes of dimension d, H_d, which are a particular case of G_d(n₁,…,n_d) in which there are only 2 vertices in each dimension. In that case, the bounds we obtain differ by a multiplicative constant equal to 2.     

The bottleneck k-MST

The k-MST is a well known NP-hard problem and several approximation algorithms exist to solve this problem with a guaranteed performance bound. A closely related problem, called the bottleneck k-MST (BMST(k)) can however be solved in O(mlogn) time on graph with n nodes and m edges. We propose two algorithms to solve BMST(k), one of complexity O(m+nlogn) and the other of O(m) time. We also consider a generalization of BMST(k) which subsumes many bottleneck problems studied in the literature and show that this generalized problem can also be solved in O(m) time.     

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t∈V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n²logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n²logn).In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n²loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n²loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs.Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.     

Characterizing r-perfect codes in direct products of two and three cycles

An r-perfect code of a graph G=(V,E) is a set C⊆V such that the r-balls centered at vertices of C form a partition of V. It is proved that the direct product of Cm and Cn (r?1, m,n?2r+1) contains an r-perfect code if and only if m and n are each a multiple of ²(r+1)+r² and that the direct product of Cm, Cn, and C? (r?1, m,n,??2r+1) contains an r-perfect code if and only if m, n, and ? are each a multiple of r³+³(r+1). The corresponding r-codes are essentially unique. Also, r-perfect codes in C2r×Cn (r?2, n?2r) are characterized.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Oriented colorings of partial 2-trees

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping f from V(G) to V(H), that is f(x)f(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth g?3. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11.     

Patterns for multigrid equidistributed functions: Application to general parabolas and length estimation

We show that for some special functions (called k-multigrid equidistributed functions), we can compute the limit of the frequency of patterns in the discretization of their graph, when the resolution tends to zero. This result is applied to parabolas. We deduce also that local length estimators almost never converge to the length for the parabolas.