Algorithmic Graph Theory and Perfect Graphs Martin Charles Golumbic Courant Institute of Mathematical Sciences New York University New York, New York 1980 ACADEMIC PRESS A Subsidiary of Harcourt Brace Jovanovich, Publishers New York London Toronto Sydney San Francisco COPYRIGHT © 1980, BY ACADEMIC PRESS, INC. ALL RIGHTS RESERVED. NO PART OF THIS PUBLICATION MAY BE REPRODUCED OR TRANSMITTED IN ANY FORM OR BY ANY MEANS, ELECTRONIC OR MECHANICAL, INCLUDING PHOTOCOPY, RECORDING, OR ANY INFORMATION STORAGE AND RETRIEVAL SYSTEM, WITHOUT PERMISSION IN WRITING FROM THE PUBLISHER. ACADEMIC PRESS, INC. Ill Fifth Avenue, New York, New York 10003 United Kingdom Edition published by ACADEMIC PRESS, INC. (LONDON) LTD. 24/28 Oval Road, London NW1 7DX Library of Congress Cataloging in Publication Data Golumbic, Martin Charles. Algorithmic graph theory and perfect graphs. (Computer science and applied mathematics) Includes bibliographies and index. 1. Graph theory. I. Title. QA166.G64 51Γ.5 79-22956 ISBN 0-12-289260-7 PRINTED IN THE UNITED STATES OF AMERICA 80 81 82 83 9 8 7 6 5 4 3 2 1 Dedicated to my parents onp'n mn TOD1? p^amVia, ρπχ·> p D-QX pan ^ma na »asm Foreword Research in graph theory and its applications has increased considerably in recent years. Typically, the elaboration of new theoretical structures has moti- vated a search for new algorithms compatible with those structures. Rather than the arduous and systematic study of every new concept definable with a graph, the main task for the mathematician is to eliminate the often arbitrary and cum- bersome definitions, keeping only the "deep" mathematical problems. Of course, the deep problems may well be elusive; indeed, there have been many definitions (from Dieudonné, among others) of what a deep problem is. In graph theory, it should relate to a variety of other combinatorial structures and must therefore be connected with many difficult practical problems. Among these will be problems that classical algebra is not able to solve completely or that the computer scientist would not attack by himself. This book, by Martin Golumbic, is intended as an introduction to graph theory through just these practical problems, nearly all of them related to the structure of permutation graphs, interval graphs, circle graphs, threshold graphs, perfect graphs, and others. The reader will not find motivations drawn from number theory, as is usual for most of the extremal graph problems, or from such refinements of old riddles as the four-color problem and the Hamiltonian tour. Instead, Golumbic has selected practical problems that occur in operations research, scheduling, econometrics, and even genetics or ecology. The author's point of view has also enjoyed increasing favor in the area of complexity analysis. Each time a new structure appears, the author immediately devotes some effort to a description of efficient algorithms, if any are known to exist, and to a determination of whether a proposed algorithm is able to solve the problem within a reasonable amount of time. xill xiv Foreword Certainly a wealth of literature on graph theory has developed by now. Yet it is clear that this book brings a new point of view and deserves a special place in the literature. CLAUDE BERGE Preface The notion of a "perfect" graph was introduced by Claude Berge at the birth of the 1960s. Since that time many classes of graphs, interesting in their own right, have been shown to be perfect. Research, in the meantime, has proceeded along two lines. The first line of investigation has included the proof of the perfect graph theorem (Theorem 3.3), attempts at proving the strong perfect graph conjecture, studies of critically imperfect graphs, and other aspects of perfect graphs. The second line of approach has been to discover mathematical and algorithmic properties of special classes of perfect graphs: comparability graphs, triangulated graphs, and interval graphs, to name just a few. Many of these graphs arise quite naturally in real-world applications. For example, uses include optimization of computer storage, analysis of genetic structure, synchro- nization of parallel processes, and certain scheduling problems. Recently it appeared to me that the time was ripe to assemble and organize the many results on perfect graphs that are scattered throughout the literature, some of which are difficult to locate. A serious attempt has been made to coordinate the mélange of some 200 papers referenced here in a manner that would make the subject more accessible to those interested in algorithmic and algebraic graph theory. I have tried to include most of the important results that are currently known. In addition, a few new results and new proofs of old results appear throughout the text. In particular, Chapter 9, on superperfect graphs, contains results due to Alan J. Hoffman, Ellis Johnson, Larry J. Stockmeyer, and myself that are appearing in print for the first time. The emphasis of any book naturally reflects the bias of the author. As a mathe- matician and computer scientist, I am doubly biased. First, I have tried to present a rigorous and coherent theory. Proofs are constructive and are streamlined as much as possible. The notation has been chosen to facilitate these matters. Sec- ond, I have directed much attention to the algorithmic aspects of every problem. xv xvi Preface Algorithms are expressed in a manner that will make their adaptation to a partic- ular programming language relatively easy. The complexity of every algorithm is analyzed so that some measure of its efficiency can be determined. These two approaches enhance one another very well. By exploiting the math- ematical properties satisfied a priori by a structure, one is often able to reduce the time or space complexity required to solve a problem. Conversely, the al- gorithmic approach often leads to startling theoretical results. To illustrate this point, consider the fact that certain NP-complete problems become tractable when restricted to certain classes of perfect graphs, whereas the algorithm for recognizing comparability graphs gives rise to a matroid associated with the graph. A glance at the table of contents will provide a rough outline of the topics to be discussed. The first two chapters are introductory in the sense that they provide the foundations, respectively, of the graph theoretic notions and the algorithmic design and analysis techniques that will be used in the remaining chapters. The reader may wish to read these two chapters quickly and refer to them as needed. The chapters are structured in such a way that the book will be suitable as a textbook in a course on algorithmic combinatorics, graph theory, or perfect graphs. In addition, the book will be very useful for applied mathematicians and computer scientists at the research level. Many applications of the theoretical and computational aspects of the subject are described throughout the text. At the end of each chapter there are numerous exercises to test the reader's understanding and to introduce further results. An extensive bibliography follows each chapter, and, when possible, the Mathematical Reviews number is included for further reference. The topics covered in this book have been chosen to fill a vacuum in the literature, and their interrelation and importance will become evident as early as Section 1.3. Since the intersection of this volume with the traditional material covered by most graph theory books has been designed to be small, it is highly recommended that the serious student augment his studies with one of these excellent textbooks. A one-year course with two concurrent texts is suggested. MARTIN CHARLES GOLUMBIC Acknowledgments I would like to express my gratitude to the many friends and colleagues who have assisted me in this project. Special thanks are due to Claude Berge for the kind words that introduce this volume. I am happy to acknowledge the help received from Mark Buckingham, particularly in Chapters 3 and 11. He is the coauthor of Sections 3.3-3.5. The suggestions and critical comments of my "trio" of students, Clyde Kruskal, Larry Rudolph, and Elia Weixelbaum, led to numerous improvements in the exposition. Over the past three years I have been fortunate to receive support from the Courant Institute of Mathematical Sci- ences, the National Science Foundation, the Weizmann Institute of Science, and l'Université de Paris VI. I would also like to express my appreciation to Alan J. Hoffman for many interesting discussions and for his help with the material in Chapter 9. My thanks go to Uri Peled, Fred S. Roberts, Allan Gottlieb, W. T. Trotter, Peter L. Ham- mer, and Lâszlo Lovâsz for their comments, as well as to Lisa Sabbia Walsh, Daniel Gruen, and Joseph Miller for their assistance. I am also indebted to my teacher, Samuel Eilenberg, for the guidance, insight, and kindness shown me during my days at Columbia University. But the greatest and most crucial help has come from my wife Lynn. Although not a mathematician, she managed to unconfound much of this mathematician's gibberish. She also "axed" some of my worst (best) jokes, much to my dismay. More importantly, she has been the rock on which I have always relied for en- couragement and inspiration, during our travels and at home, in the course of the research and writing of this book. As it is written in Proverbs: ♦nrwV^y Ton-rrnrn ,n&ana nnns rrs ♦n^D^y n^y ηκι >π itrw man.man xvli List of Symbols yage Symbol Meaning 1 V* For all x. 1 3j There exists a >>. 1 Λ*Χ x is a member of X 1 /1ÇX /4 is a jutef of X 1 £CX Z? is a proper subset of X 1 1*1 The cardinality of a set X 1 /in B The intersection of /I and Ä 1 AUB The Hrt/o/i of A and Ä 2 A + B The union of disjoint sets /I and Ä 2 0 The empty set. 2 ^(X) The power set of X 4 vx w The Cartesian product of sets F and W. 19 SIT Sets S and T overlap; S ΠΤΦ0, SÇT, and Γ£5. 3 G = (V,E) The graph G with vertex set V and edge set Ε. 8 G = (X X,E) The bipartite graph G with vertex set X1+X2 U 2 where each X,· is stable. 5 (Vs,S) The subgraph spanned by a subset 5" of edges. 6 GA=(A,EA) The subgraph induced by a subset /I of vertices. 3 Adj(v) The adjacency set of vertex v. 6 Adj^(v) The adjacency set restricted to A; AdjXv) = Adj(v)Ply4. 3 N(v) The neighborhood of vertex V\ N(v) = {v} +Adj(v). 7 Ay) The out-degree of vertex v. 7 <T(v) The in-degree of vertex v. 7 <«v) The degree of vertex v in an undirected graph. 4 ^1 The reversal of a set E of edges. 4 £ The symmetric closure of a set E of edges. 4 al The undirected edge {ab}U{ba}. 7 \\E\\ In an undirected graph G = (V,E) we define \\E\\ = \ \E\, 4 G The complement of an undirected graph G. 4 G^G' Graphs G and G' are isomorphic. 6 *(G) The c/iV/we number of G. 6 k{G) The clique cover number of G. xix XX List of Symbols 6 <*(G) The stability number of G. 7 X(G) The chromatic number of G. 113 t{G) The number of transitive orientations of G. 126 r(G) The rank of the r*-matroid of G. 220 B(G) The threshold dimension of G. 203 x(G;w) The interval chromatic number of a weighted graph (G;w). 206 w(G\w) The maximum weighted clique number of (G\w). 9 K The complete graph on n vertices. n 9 Cn The chordless cycle on n vertices. 9 Pn The chordless path graph on n vertices. 9 A.m,n The complete bipartite graph onw+n vertices partitioned into an m-stable set and an n-stable set. 9 K\,n The star graph on H + 1 vertices. 9 mKn m disjoint copies of K„. 47 GiXG The Cartesian product of graphs G\ and Gi. 2 77 G H The normal product of graphs G and H. 109 HQ[H\ ,. , H„] The composition of graphs. 95 ^ The class of undirected graphs satisfying the property that every odd cycle of length greater than or equal to 5 has at least two chords. 105 Γ The forcing relation on edges. 106 Γ* The reflexive, transitive closure of Γ. 106 J(G) The collection of implication classes of G. 106 S{G) The collection of color classes of G. 135 #{P) The collection of linear extensions of a partial order P. 135 dim(P) The dimension of a partial order P. 157 G[n] The permutation graph of π. 235 Η[π] The stack sorting graph of π. 157 -l The inverse of the permutation π. π 158 πρ The reversal of the permutation π. 228 LU The shuffle product. 236 M The class of stack sorting graphs. 23 0(f(m)) Computational complexity on the order offlm). 26 P The class of deterministic polynomial-time problems. 27 NP The class of nondeterministic polynomial-time problems. 27 n,<n Problem Πι is polynomially transformable to problem IL. 32 Λ 2 The null or undefined symbol in an algorithm. 176 r = r The Pg-trees T and T are equivalent. 177 mS) The collection of all permutations π of X such that the members of each subset hJ occur consecutively in π where SQ &{X). 53 G oh The graph G multiplied by the vector h. 62 Un The H-dimensional vector space over the real numbers. 62 P(A) The polyhedron of matrix A. 62 Pi(*) The integral polyhedron of matrix A. 59 1 The vector of all ones. 62 0 The vector of all zeros. 60 J The matrix of all ones. 60 I The identity matrix. 256 G(M) The graph of matrix M. 256 B(M) The bipartite graph of matrix M.