Gear composition and the stable set polytope

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of when G is claw-free.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

On the stable set polytope of a series-parallel graph

We give a short proof of Chvátal's conjecture that the nontrivial facets of the stable set polytope of a series-parallel graph all come from edges and odd holes.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and by CP Rail.     

A model of the coNP-complete non-Hamilton tour decision problem for directed graphs

A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope P^n–1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of P^n–1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G_n, a polynomial sized linear system F⁽ⁿ⁾ is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G_n. The non-Hamilton tour decision problem is modeled by F⁽ⁿ⁾ such that G_n is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F⁽ⁿ⁾ is P^n–1. The decision problem Is the projection of the solution set of F⁽ⁿ⁾=P^n–1? is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.Dedicated to the 250+ families in Kelowna BC, who lost their homes due to forest fires in 2003.I visited Ted at his home in Kelowna during this time - his family opened their home to evacuees and we shared happy and sad times with many wonderful people.     

Polynomially solvable cases for the maximum stable set problem

We describe two classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedure which, at each step, builds from a graph G a new graph G′ which has fewer vertices and has the property that (G′) = (G) − 1. For the second class, it can be decided in polynomial time whether there exists a stable set of given size k.     

Characterizing and bounding the imperfection ratio for some classes of graphs

Perfect graphs constitute a well-studied graph class with a rich structure, which is reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) equals the fractional stable set polytope QSTAB(G). The dilation ratio of the two polytopes yields the imperfection ratio of G. It is NP-hard to compute and, for most graph classes, it is even unknown whether it is bounded. For graphs G such that all facets of STAB(G) are rank constraints associated with antiwebs, we characterize the imperfection ratio and bound it by 3/2. Outgoing from this result, we characterize and bound the imperfection ratio for several graph classes, including near-bipartite graphs and their complements, namely quasi-line graphs, by means of induced antiwebs and webs, respectively.      

The stable set problem and the thinness of a graph

We introduce a poly-time algorithm for the maximum weighted stable set problem, when a certain representation is given for a graph. The algorithm generalizes the algorithm for interval graphs and that for graphs with bounded pathwidth. By a suitable application to the frequency assignment problem, we improved several solutions to relevant benchmark instances.     

A note on the disjunctive index of joined a-perfect graphs

In this paper we present a lower bound of the disjunctive rank of the facets describing the stable set polytope of joined a-perfect graphs. This class contains near-bipartite, t-perfect, h-perfect and complement of fuzzy interval graphs, among others. The stable set polytope of joined a-perfect graphs is described by means of full rank constraints of its node induced prime antiwebs. As a first step, we completely determine the disjunctive rank of all these constraints. Using this result we obtain a lower bound of the disjunctive index of joined a-perfect graphs and prove that this bound can be achieved. In addition, we completely determine the disjunctive index of every antiweb and observe that it does not always coincide with the disjunctive rank of its full rank constraint.     

The stable set problem and the lift-and-project ranks of graphs

We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovász and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N₀-, N-, or N₊-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N₀- or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N₊-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N₊-rank of a graph.Research of these authors was supported in part by a PREA from Ontario, Canada and research grants from NSERC.Mathematics Subject Classification (2000): 0C10, 90C22, 90C27, 47D20     

Complete solutions to the Oberwolfach problem for an infinite set of orders

Let n3 and let F be a 2-regular graph of order n. The Oberwolfach problem OP(F) asks for a 2-factorisation of K_n if n is odd, or of K_n−I if n is even, in which each 2-factor is isomorphic to F. We show that there is an infinite set of primes congruent to such that OP(F) has a solution for any 2-regular graph F of order . We also show that for each of the infinitely many with prime, OP(F) has a solution for any 2-regular graph F of order n.     

Facets and lifting procedures for the set covering polytope

Given a family of subsets of an arbitrary groundsetE, acover of is any setC E having non-empty intersection with every subset in. In this paper we deal with thecovering polytope, i.e., the convex hull of the incidence vectors of all the covers of. In Section 2 we review all the known properties of the covering polytope. In Sections 3 and 4 we introduce two new classes of non-Boolean facets of such a polytope. In Sections 5 and 6 we describe some non-sequential lifting procedures. In Section 7 a generalization of the notion ofweb introduced by L.E. Trotter is presented together with the facets of the covering polytope produced by such a structure.Moreover, the strong connections between several combinatorial problems and the covering problem are pointed out and, exploiting those connections, some examples are presented of new facets for the Knapsack and Acyclic Subdigraph polytopes.     

The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

Using critical sets to solve the maximum independent set problem

A method that utilizes the polynomially solvable critical independent set problem for solving the maximum independent set problem on graphs with a nonempty critical independent set is developed. The effectiveness of the proposed approach on large graphs with large independence number is demonstrated through extensive numerical experiments.     

Decomposition techniques for the ocean wave identification problem

This paper deals with the solution of the ocean wave identification problem by means of decomposition techniques. A discrete formulation is assumed. An ocean test structure is considered, and wave elevation and velocities are assumed to be measured with a number of sensors. Within the frame of linear wave theory, a Fourier series model is chosen for the wave elevation and velocities. Then, the following problem is posed (Problem P): Find the amplitudes of the various wave components of specified frequency and direction, so that the assumed model of wave elevation and velocities provides the best fit to the measured data. Here, the term best fit is employed in the least-square sense over a given time interval.Problem P is numerically difficult because of its large size 2MN, whereM is the number of frequencies andN is the number of directions. Therefore, both the CPU time and the memory requirements are considerable (Refs. 7–12).In order to offset the above difficulties, decomposition techniques are employed in order to replace the solution of Problem P with the sequential solution of two groups of smaller subproblems. The first group (Problem F) involvesS subproblems, having size 2M, whereS is the number of sensors andM is the number of frequencies; theseS subproblems are least-square problems in the frequency domain. The second group (Problem D) involvesM subproblems, having size 2N, whereM is the number of frequencies andN is the number of directions; theseM subproblems are least-square problems in the direction domain.In the resulting algorithm, called the discrete formulation decomposition algorithm (DFDA, Ref. 2), the linear equations are solved with the help of the Householder transformation in both the frequency domain and the direction domain. By contrast, in the continuous formulation decomposition algorithm (CFDA, Ref. 1), the linear equations are solved with Gaussian elimination in the frequency domain and with the help of the Householder transformation in the direction domain.Mathematically speaking, there are three cases in which the solution of the decomposed problem and the solution of the original, undecomposed problem are identical: (a) the case where the number of sensors equals the number of directions; (b) the case where Problem P is characterized by a vanishing value of the functional being minimized; and (c) the case where the wave component periods are harmonically related to the sampling time.Numerical experiments concerning the OTS platform and the Hondo-A platform show that the decomposed scheme is considerably superior to the undecomposed scheme; that the discrete formulation is considerably superior to the continuous formulation; and that the accuracy can be improved by proper selection of the sampling time as well as by proper choice of the number and the location of the sensors. In particular, the choice of the sensor location for the Hondo-A platform is discussed.This work was supported by Exxon Production Research Company, Houston, Texas. This paper is based on Refs. 1–6 and is a continuation of the work presented in Refs. 7–12.