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.      

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.     

On the set covering polyhedron of circulant matrices

A well known family of minimally nonideal matrices is the family of the incidence matrices of chordless odd cycles. A natural generalization of these matrices is given by the family of circulant matrices. Ideal and minimally nonideal circulant matrices have been completely identified by Cornuéjols and Novick [G. Cornuéjols, B. Novick, Ideal 0 - 1 matrices, Journal of Combinatorial Theory B 60 (1994) 145–157]. In this work we classify circulant matrices and their blockers in terms of the inequalities involved in their set covering polyhedra. We exploit the results due to Cornuéjols and Novick in the above-cited reference for describing the set covering polyhedron of blockers of circulant matrices. Finally, we point out that the results found on circulant matrices and their blockers present a remarkable analogy with a similar analysis of webs and antiwebs due to Pêcher and Wagler [A. Pêcher, A. Wagler, A construction for non-rank facets of stable set polytopes of webs, European Journal of Combinatorics 27 (2006) 1172–1185; A. Pêcher, A. Wagler, Almost all webs are not rank-perfect, Mathematical Programming Series B 105 (2006) 311–328] and Wagler [A. Wagler, Relaxing perfectness: Which graphs are ‘Almost’ perfect?, in: M. Groetschel (Ed.), The Sharpest Cut, Impact of Manfred Padberg and his work, in: SIAM/MPS Series on Optimization, vol. 4, Philadelphia, 2004; A. Wagler, Antiwebs are rank-perfect, 4OR 2 (2004) 149–152].     

A lower bound on the Chvátal-rank of Antiwebs

In [Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of linear relaxations of the stable set polytope, International Transactions in Operational Research 17 (2010), pp. 827–849; Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of Antiwebs, Electronic Notes in Discrete Mathematics 36 (2010), pp. 183–190] we study the Chvátal-rank of the edge constraint and the clique constraint stable set polytopes related to antiwebs. We present schemes for obtaining both upper and lower bounds. Moreover, we provide an algorithm to compute the exact values of the Chvátal-rank for all antiwebs with up to 5,000 nodes. Here we prove a lower bound as a closed formula and discuss some cases when this bound is tight.     

On Balanced Graphs

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Received: April, 2004     

Crown reductions for the Minimum Weighted Vertex Cover problem

The paper studies crown reductions for the Minimum Weighted Vertex Cover problem introduced recently in the unweighted case by Fellows et al. [Blow-Ups, Win/Win's and crown rules: some new directions in FPT, in: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG’03), Lecture notes in computer science, vol. 2880, 2003, pp. 1-12, Kernelization algorithms for the vertex cover problem: theory and experiments, in: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, Louisiana, January 2004, pp. 62-69]. We describe in detail a close relation of crown reductions to Nemhauser and Trotter reductions that are based on the linear programming relaxation of the problem. We introduce and study the so-called strong crown reductions, suitable for finding (or counting) all minimum vertex covers, or finding a minimum vertex cover under some additional constraints. It is described how crown decompositions and strong crown decompositions suitable for such problems can be computed in polynomial time. For weighted König-Egerváry graphs (G,w) we observe that the set of vertices belonging to all minimum vertex covers, and the set of vertices belonging to no minimum vertex covers, can be efficiently computed.Further, for some specific classes of graphs, simple algorithms for the MIN-VC problem with a constant approximation factor r<2 are provided. On the other hand, we conclude that for the regular graphs, or for the Hamiltonian connected graphs, the problem is as hard to approximate as for general graphs.It is demonstrated how the results about strong crown reductions can be used to achieve a linear size problem kernel for some related vertex cover problems.     

Independent sets and 2‐factors in edge‐chromatic‐critical graphs

In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for critical graphs with many edges, and determine upper bounds for the size of independent vertex sets in those graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113–118, 2004     

Forbidden minors for wye‐delta‐wye reducibility

A graph is Y Δ Y reducible if it can be reduced to a single vertex by a sequence of series‐parallel reductions and Y Δ Y transformations. The class of Y Δ Y reducible graphs is minor closed. We found a large number of minor minimal Y Δ Y irreducible graphs: a family of 57578 31‐edge graphs and another 40‐edge graph. It is still an open problem to characterize Y Δ Y reducible graphs in terms of a finite set of forbidden minors. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 317–321, 2004     

Graph Products,Fourier Analysis and Spectral Techniques

We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others, complete graphs, line graphs of regular graphs which contain a perfect matching and Kneser graphs. In many cases this also characterizes the optimal colorings of these products.We show that the independent sets induced by the base graph are the only maximum-size independent sets. Furthermore we give a qualitative stability statement: any independent set of size close to the maximum is close to some independent set of maximum size.Our approach is based on Fourier analysis on Abelian groups and on Spectral Techniques. To this end we develop some basic lemmas regarding the Fourier transform of functions on generalizing some useful results from the case.     

König–Egerváry Graphs are Non-Edmonds

König–Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125–130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors ${{\bf{x}}\in\mathbb R^E}K?nig–Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125–130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors x ? \mathbb R^E{{\bf{x}}\in\mathbb R^E} satisfying two families of constraints: ‘vertex saturation’ and ‘blossom’. Graphs for which the latter constraints are implied by the former are termed non-Edmonds. This note presents two proofs—one combinatorial, one algorithmic—of its title’s assertion. Neither proof relies on the characterization of non-Edmonds graphs due to de Carvalho et al. (J Combin Theory Ser B 92:319–324, 2004).     

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004     

Algebraic structures on graphs

In this paper we consider directed graphs with algebraic structures: group-graphs, ringgraphs, involutorial graphs, affine graphs, graphs of morphisms between graphs, graphs of reduced paths of an involutorial graph, etc. We show also how several well-known algebraic constructions can be carried over to graphs. As a typical example we generalize the construction of the group of automorphisms of a set, by constructing a group-graph associated with any given graphΓ. It is the group-graph of reduced paths of the involutorial graph associated to the graph of automorphisms ofΓ.     

Periodic schedules for linear precedence constraints

We consider the computation of periodic cyclic schedules for linear precedence constraints graphs: a linear precedence constraint is defined between two tasks and induces an infinite set of usual precedence constraints between their executions such that the difference of iterations is a linear function. The objective function is the minimization of the maximal period of a task.We recall first that this problem may be modelled using linear programming. A polynomial algorithm is then developed to solve it for a particular class of linear precedence graphs called unitary graphs. We also show that a periodic schedule may not exist for unitary graphs. In the general case, a decomposition of the linear precedence graph into unitary components is computed and we assume that a periodic schedule exists for each of these components. Lower bounds on the periods are exhibited and we show that an optimal periodic schedule may not achieve them. The notion of quasi-periodic schedule is then introduced and we prove that this new class of schedules always reaches these bounds.     

Constructing the reachability set for a control problem with phase constraints

A method is proposed for describing the reachability set in a phase-constrained control problem. Sufficient conditions are obtained when the reachability set in a phase-constrained control problem is the intersection of two sets: the reachability set for the corresponding problem without phase constraints and the set of phase constraints. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 397–399, 2004.     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

On the online track assignment problem

This paper aims to start an analytical study of the computational complexity of some online shunting problems. We analyze the following problem. Consider a train station consisting of a set of parallel tracks. Each track can be approached from one side only or from both sides and the number of trains per track may be limited or not. The departure times of the trains are fixed according to a given time table. The problem is to assign a track to each train as soon as it arrives and such that it can leave the station on time without being blocked by any other train.We show that this problem can be modeled with online coloring of graphs. Depending on the constraints, the graphs can be overlap graphs (also known as circle graphs) or permutation graphs, and the coloring can be bounded or classical. This paper covers several combinations of these cases.     

Dominating and large induced trees in regular graphs

Recently Chen et al. [Tree domination in graphs, Ars Combin. 73 (2004) 193-203] asked for characterizations of the class of graphs and the class of regular graphs that have an induced dominating tree, i.e. for which there exists a dominating set that induces a tree.We give a somewhat negative answer to their question by proving that the corresponding decision problems are NP-complete. Furthermore, we prove essentially best-possible lower bounds on the maximum order of induced trees in connected cacti of maximum degree 3 and connected cubic graphs.Finally, we give a forbidden induced subgraph condition for the existence of induced dominating trees.     

Material compatibility constraints for make-to-order production planning

This paper defines a set of material compatibility constraints for use in order promising mixed integer programs. The constraints always represent a necessary condition for compatibility and, in certain cases, are both necessary and sufficient. The underlying analysis represents incompatibilities using bipartite graphs and applies results from the perfectly matchable subgraph polytope.