Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

Spanners for bounded tree-length graphs

This paper concerns construction of additive stretched spanners with few edges for n$n$-vertex graphs having a tree-decomposition into bags of diameter at most δ$\delta$, i.e., the tree-length δ$\delta$ graphs. For such graphs we construct additive 2δ$2\delta$-spanners with O(δn+nlogn)$O(\delta n+nlogn)$ edges, and additive 4δ$4\delta$-spanners with O(δn)$O\left(\delta n\right)$ edges. This provides new upper bounds for chordal graphs for which δ=1$\delta =1$. We also show a lower bound, and prove that there are graphs of tree-length δ$\delta$ for which every multiplicative δ$\delta$-spanner (and thus every additive (δ−1)$(\delta -1)$-spanner) requires Ω(n^1+1/Θ(δ))$\Omega \left(n^{1+1/\Theta \left(\delta \right)}\right)$ edges.     

Packing triangles in bounded degree graphs

We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (respectively 4), whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (respectively 5) or more.     

The strict bounded real lemma in infinite dimensions

The strict bounded real lemma is generalized to an infinite-dimensional setting. This relates the existence of a stabilizing solution to a Riccati equation to an H∞-norm bound and to the existence of a solution to a Riccati inequality.     

A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

This paper concerns a domination problem in graphs with parity constraints. The task is to find a subset of the vertices with minimum cost such that for every vertex the number of chosen vertices in its neighbourhood has a prespecified parity. This problem is known to be ${\mathcal NP}$ -hard for general graphs. A linear time algorithm was developed for series-parallel graphs and trees with unit cost and restricted to closed neighbourhoods. We present a linear time algorithm for the parity domination problem with open and closed neighbourhoods and arbitrary cost functions on graphs with bounded treewidth and distance-hereditary graphs.     

Linearly many faults in Cayley graphs generated by transposition trees

We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices.     

Exponentially convergent Fourier-Chebshev quadrature schemes on bounded and infinite intervals

The Clenshaw-Curtis method for numerical integration is extended to semi-infinite ([0, ] and infinite [-∞, ] intervals. The common framework for both these extensions and for integration on a finite interval is to (1) map the integration domain tol [0,], (2) compute a Fourier sine or cosine approximation to the transformd integrand via interpolation, and (3) integrate the approximation. The interpolation is most easily performed via the sine or cosine cardinal functions, which are discussed in the appendix. The algorithm is mathematically equivalent to expanding the integrand in (mapped or unmapped) Chebyshev polynomials as done by Clenshaw and Curtis, but the trigonometric approach simplifies the mechanics. Like Gaussian quadrature, the error for the change-of-coordinates Fourier method decreases exponentially withN, the number of grid points, but the generalized Curtis-Clenshaw algorithm is much easier to program than Gaussian quadrature because the abscissas and weights are given by simple, explicit formulas.     

Speeding up dynamic transitive closure for bounded degree graphs

In this paper we present an algorithm for solving two problems in dynamically maintaining the transitive closure of a digraph: In the first problem a sequence of edge insertions is performed on an initially empty graph, interspersed withp transitive closure queries of the form: is there a path froma tob in the graph. Our algorithm solves this problem in timeO (dm ^*+p), whered is the maximum outdegree of the resulting graphG andm ^* is the number of edges in the transitive closure ofG. In the second problem, a sequence of edge deletions is performed on anacyclic graph, interspersed withp transitive closure queries. Once again we solve this problem in timeO (dm ^*+p), whered is the maximum outdegree of the initial graphG andm ^* is the number of edges in the transitive closure ofG. For bounded degree graphs, this improves upon previous results. Our algorithms also work when insertions and deletions to the graph are intermixed. Finally, we show how to implement the operation findpath (x, y) which retrieves some path fromx toy in time proportional to the length of the path.     

The monadic second-order logic of graphs,II: Infinite graphs of bounded width

A countable graph can be considered as the value of a certain infinite expression, represented itself by an infinite tree. We establish that the set of finite or infinite (expression) trees constructed with a finite number of operators, the value of which is a graph satisfying a property expressed in monadic second-order logic, is itself definable in monadic second-order logic. From Rabin's theorem, the emptiness of this set of (expression) trees is decidable. It follows that the monadic second-order theory of an equational graph, or of the set of countable graphs of width less than an integerm, is decidable. This work has been supported by the “Programme de Recherches Coordonnées: Mathématiques et Informatique.” Reprints can be requested by electronic mail at mcvax!inria!geocub!courcell (on UUCP network) or courcell@geocub.greco-prog.fr. Unité de Recherche associée au C.N.R.S. no. 726.     

Efficient frequent connected subgraph mining in graphs of bounded tree-width

The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded tree-width graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.     

Game chromatic number of graphs with locally bounded number of cycles

We consider the coloring game and the marking game on graphs with bounded number of cycles passing through any edge. We prove that the game coloring number of a graph G is at most c+4, if every edge of G belongs to at most c different cycles. This result covers two earlier bounds on the game coloring number: for trees (c=0) and for cactuses (c=1).     

Answering exact distance queries on real-world graphs with bounded performance guarantees

The ability to efficiently obtain exact distance information from both directed and undirected graphs is desired by many real-world applications. In this work, we unified the query indexing efforts on directed and undirected graphs into one by proposing the TreeMap approach. Our approach has very tight bounds on query time, index size, and construction time for answering queries on both directed and undirected graphs. The query time complexity is close to constant for graphs with a small width of tree decomposition, and the index construction can be completed without materializing the distance matrix or other high-cost operations. In the empirical study, we demonstrated that the TreeMap approach in general performs much better than competitive methods in indexing real graphs for answering exact distance queries.     

Decomposition of sparse graphs into two forests, one having bounded maximum degree

Let G be a graph. The maximum average degree of G, written Mad(G), is the largest average degree among the subgraphs of G. It was proved in Montassier et al. (2010) [11] that, for any integer k?0, every simple graph with maximum average degree less than admits an edge-partition into a forest and a subgraph with maximum degree at most k; furthermore, when k?3 both subgraphs can be required to be forests. In this note, we extend this result proving that, for k=4,5, every simple graph with maximum average degree less than mk admits an edge-partition into two forests, one having maximum degree at most k (i.e. every graph with maximum average degree less than (resp. ) admits an edge-partition into two forests, one having maximum degree at most 4 (resp. 5)).     

Infinite games on finitely coloured graphs with applications to automata on infinite trees

We examine a class of infinite two-person games on finitely coloured graphs. The main aim is to construct finite memory winning strategies for both players. This problem is motivated by applications to finite automata on infinite trees. A special attention is given to the exact amount of memory needed by the players for their winning strategies. Based on a previous work of Gurevich and Harrington and on subsequent improvements of McNaughton we propose a unique framework that allows to reestablish and to improve various results concerning memoryless strategies due to Emerson and Jutla, Mostowski, Klarlund.     

Finite-time consensus for multi-agent systems with globally bounded convergence time under directed communication graphs

In this paper, we study the finite-time consensus problems with globally bounded convergence time also known as fixed-time consensus problems for multi-agent systems subject to directed communication graphs. Two new distributed control strategies are proposed such that leaderless and leader-follower consensus are achieved with convergence time independent on the initial conditions of the agents. Fixed-time formation generation and formation tracking problems are also solved as the generalizations. Simulation examples are provided to demonstrate the performance of the new controllers.     

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #Sat to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. Consequently, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.