Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. Received February 18, 1997; revised February 23, 1998.     

On-line coloring and cliques covering for KK s,t -free graphs

The problem of on-line coloring of an arbitrary graphs is known to be hard. Here we consider the problem of on-line coloring in the simplified situation where the input graph is KK_s,t-free. We show that the on-line coloring algorithm with the First Fit strategy of proposed by Capponi and Pilotto in [1] is the best one for KK_1,t-free graphs (t≥3). A.Capponi and C.Pilotto have shown that this algorithm achieves a competitive ratio of t−1 while we show that it is the best possible. However for the family of KK_s,t-free graphs (s≥2, t≥2) there exists no on-line coloring algorithm with a competitive function. The problem of an on-line cliques covering for these families is hard. There exists no on-line cliques covering algorithm with a competitive function for the family of KK_s,t-free graphs (s≥ 1, t≥3). The additional assumption that the input graph is given in a connected way does not help a lot and does not change our results described above.     

Spanners in sparse graphs

A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that on unweighted planar graphs deciding whether G admits a tree t-spanner is polynomial time solvable for t?3 and is NP-complete when t is part of the input. They also left as an open problem if the problem is polynomial time solvable for every fixed t?4. In this work we resolve the open question of Fekete and Kremer by proving much more general results:

• • 

  The problem of finding a t-spanner of treewidth at most k in a given planar graph G is fixed parameter tractable parameterized by k and t. Moreover, for every fixed t and k, the running time of our algorithm is linear.

• • 

  Our technique allows to extend the result from planar graphs to much more general classes of graphs. An apex graph is a graph that can be made planar by the removal of a single vertex. We prove that the problem of finding a t-spanner of treewidth k is fixed parameter tractable on graphs that do not contain some fixed apex graph as a minor, i.e. on apex-minor-free graphs. The class of apex-minor-free graphs contains planar graphs and graphs of bounded genus.

• • 

  Finally, we show that the tractability border of the t-spanner problem cannot be extended beyond the class of apex-minor-free graphs and in this sense our results are tight. In particular, for every t?4, the problem of finding a tree t-spanner is NP-complete on K6-minor-free graphs.

     

Treewidth Lower Bounds with Brambles

In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower bounds, in particular when applied to (close to) planar graphs. This work was partially supported by the Netherlands Organisation for Scientific Research NWO (project Treewidth and Combinatorial Optimisation) and partially by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4).     

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles. More specifically, we give fixed parameter tractable algorithms for Dominating Set, t -Vertex Cover (where we need to cover at least t edges) and several of their variants on graphs with girth at least five. These problems are known to be W[i]-hard for some i≥1 in general graphs. We also show that the Dominating Set problem is W[2]-hard for bipartite graphs and hence for triangle free graphs. In the case of Independent Set and several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that the Dense Subgraph problem where one is interested in finding an induced subgraph on k vertices having at least l edges, parameterized by k, is W[1]-hard even on graphs with girth at least six. Finally, we give an O(log p) ratio approximation algorithm for the Dominating Set problem for graphs with girth at least 5, where p is the size of an optimum dominating set of the graph. This improves the previous O(log n) factor approximation algorithm for the problem, where n is the number of vertices of the input graph. A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.     

Reduction Algorithms for Graphs of Small Treewidth

This paper presents a number of new ideas and results on graph reduction applied to graphs of bounded treewidth. S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese (J. Assoc. Comput. Mach.40, 1134–1164 (1993)) have shown that many decision problems on graphs can be solved in linear time on graphs of bounded treewidth, using a finite set of reduction rules. These algorithms can be used to solve problems on graphs of bounded treewidth without the need to obtain a tree decomposition of the input graph first. We show that the reduction method can be extended to solve the construction variants of many decision problems on graphs of bounded treewidth, including all problems definable in monadic second order logic. We also show that a variant of these reduction algorithms can be used to solve (constructive) optimization problems in O(n) time. For example, optimization and construction variants of I S and H C N can be solved in this way on graphs of small treewidth. Additionally, we show that the results of H. L. Bodlaender and T. Hagerup (SIAM J. Comput.27, 1725–1746 (1998)) can be applied to our reduction algorithms, which results in parallel reduction algorithms that use O(n) operations and O(log n log* n) time on an EREW PRAM, or O(log n) time on a CRCW PRAM.     

Approximation Algorithms for Treewidth

This paper presents algorithms whose input is an undirected graph, and whose output is a tree decomposition of width that approximates the optimal, the treewidth of that graph. The algorithms differ in their computation time and their approximation guarantees. The first algorithm works in polynomial-time and finds a factor-O(log OPT) approximation, where OPT is the treewidth of the graph. This is the first polynomial-time algorithm that approximates the optimal by a factor that does not depend on n, the number of nodes in the input graph. As a result, we get an algorithm for finding pathwidth within a factor of O(log OPT⋅log n) from the optimal. We also present algorithms that approximate the treewidth of a graph by constant factors of 3.66, 4, and 4.5, respectively and take time that is exponential in the treewidth. These are more efficient than previously known algorithms by an exponential factor, and are of practical interest. Finding triangulations of minimum treewidth for graphs is central to many problems in computer science. Real-world problems in artificial intelligence, VLSI design and databases are efficiently solvable if we have an efficient approximation algorithm for them. Many of those applications rely on weighted graphs. We extend our results to weighted graphs and weighted treewidth, showing similar approximation results for this more general notion. We report on experimental results confirming the effectiveness of our algorithms for large graphs associated with real-world problems.     

Diameter and Treewidth in Minor-Closed Graph Families

It is known that any planar graph with diameter D has treewidth O(D) , and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families. We show that treewidth is bounded by a function of the diameter in a minor-closed family, if and only if some apex graph does not belong to the family. In particular, the O(D) bound above can be extended to bounded-genus graphs. As a consequence, we extend several approximation algorithms and exact subgraph isomorphism algorithms from planar graphs to other graph families.     

Maximum <Emphasis Type="Italic">k</Emphasis>-Splittable <Emphasis Type="Italic">s</Emphasis>,<Emphasis Type="Italic">t</Emphasis>-Flows

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.     

Tractable cases of the extended global cardinality constraint

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) í DD(x) \subseteq D for each variable x, and a “cardinality set” K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption  FPT ≠ W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.     

Exponential Stability of Slowly Time-Varying Nonlinear Systems

Let be a time-varying vector field depending on t containing a regular and a slow time scale (α large). Assume there exist a k (τ)≥1 and a γ(τ) such that ∥x _τ(t, t ₀, x ₀)∥≤k(τ) e ^{−γ(τ)(t−t0)}∥x ₀∥, with x _τ(t, t ₀, x ₀) the solution of the parametrized system with initial state x ₀ at t ₀. We show that for α sufficiently large is exponentially stable when “on average”γ(τ) is positive. The use of this result is illustrated by means of two examples. First, we extend the circle criterion. Second, exponential stability for a pendulum with a nonlinear slowly time-varying friction attaining positive and negative values is discussed. Date received: January 22, 2000. Date revised: April 14, 2001.     

Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

Given an undirected multigraph G=(V,E), a family $\mathcal{W}Given an undirected multigraph G=(V,E), a family W\mathcal{W} of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W ? WW\in \mathcal{W} . So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k ³+n ²)(p+kn+nlog n)log k+pkn ³log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and p=|W|p=|\mathcal{W}| .     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

Allocating Weighted Jobs in Parallel

The classic balls-into-bins game considers the experiment of placing m balls independently and uniformly at random (i.u.r.) in n bins. For m=n , it is well known that the maximum load, i.e., the number of balls in the fullest bin is Θ(log n/log log n) , with high probability. It is also known (see [S2]) that a maximum load of O( m / n ) can be obtained for all m≥ n if each ball is allocated in one (suitably chosen) of two (i.u.r.) bins. Stemann presents a distributed algorithm to find the ``suitable' bin for each ball. The algorithm uses r communication rounds to achieve a maximum load of , with high probability. Adler et al. [ACMR] show that Stemann's protocol is optimal up to a constant factor for constant r . In this paper we extend the above results in two directions: we generalize the lower bound to arbitrary r≤log log n . This implies that Stemann's protocol is optimal for all r . Our key result is a generalization of Stemann's upper bound to weighted balls: Let W ^A (resp. W ^M ) denote the average (resp. maximum) weight of the balls. Furthermore, let Δ=W ^A /W ^M . Then the optimal maximum load is Ω(m/n⋅ W ^A +W ^M ) . We present a protocol that achieves a maximum load of γ⋅( m / n ⋅ W ^A +W ^M ) using O( log log n / log (γ⋅(m/n⋅Δ+1)) ) communication rounds. For uniform weights this matches the results of Stemann. In particular, we achieve a load of O( m / n ⋅ W ^A +W ^M ) using log log n communication rounds, which is optimal up to a constant factor. An extension of our lower bound shows that our algorithm also reaches a load which is within a constant factor of the optimal load in the case of weighted balls. All the balls-into-bins games model load balancing problems: the balls are jobs, the bins are resources, the task is to allocate the jobs to the resources in such a way that the maximum load is minimized. Our extension to weighted balls allows us to extend previous bounds to models where resource requirements may vary. For example, if the jobs are computing tasks, their running times may vary. Applications of such load balancing problems occur, e.g., for client-server networks and for multimedia-servers using disk arrays. Received December 23, 1997, and in final form September 9, 1998.     

Collective Tree Spanners in Graphs with Bounded Parameters

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system $\mathcal{T}(G)In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system T(G)\mathcal{T}(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ? T(G)T\in\mathcal{T}(G) exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of O(?n)O(\sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree (2w)(2\mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree (2?c/2?w)(2\lfloor c/2\rfloor\mathsf{w}) -spanners and a system of 4log ₂ n collective additive tree (2(?c/3?+1)w)(2(\lfloor c/3\rfloor +1)\mathsf {w}) -spanners (here, w\mathsf{w} is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree (2w)(2\mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.     

Isomorphic tree spanner problems

A treet-spanner, wheret is a positive integer, of a graph G is a spanning tree in which the distance between the two ends of every edge ofG is at mostt. This notion is motivated by applications in distributed systems and communication networks. This paper is concerned with the problem of determining whether a graph contains a tree t-spanner isomorphic to a given tree. It is shown that the problem fort=2 is solvable in O(n^3.5) time for 2-connected graphs, whereas the problem for any fixed integert 3 is NP-complete, even for 2-connected bipartite graphs.Financial support for this research was received from the Natural Sciences and Engineering Research Council of Canada.     

Numerical approximation of an elliptic-parabolic equation arising in environment

We prove the convergence of a finite volume scheme for the Richards equation β(p)_t-div(λ(β(p)) (νp-ρg) =0, together with a Dirichlet boundary condition and an initial condition, in a bounded domain. We consider the hydraulic charge u=-z as the main unknown function so that no upwinding is necessary. The convergence proof is based on the strong convergence in L² of the water saturation β(p), which one obtains by estimating differences of space and time translates and applying Kolmogorov’s theorem. Received: 30 April 1999 / Revised version: 17 June 1999     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.