Suboptimal colorings and solution of large chromatic scheduling problems

Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution will be reported), see [Cul] for a list of over 450 references. The graph coloring problem involves coloring the vertices of a given graph in such a way that two adjacent vertices never share the same color. The goal is to find the smallest number of colors needed to color all vertices in a fashion that satisfies this requirement. This number is called chromatic number and is denoted by Χ. In the first chapter, we present our research on suboptimal colorings and graphs which can be colored in such a way that the number of different colors appearing on the closed neighborhood (a vertex plus its neighbors) of any vertex v is less than Χ. We call such graphs oligomatic. The most interesting result is the following: given a graph and a coloring using Χ + p colors, there exists a vertex v such that there are at least Χ different colors among all vertices which are at a distance of [p/2] + 1 or less from v. We also study the existence of oligomatic graphs in special classes. Additionally, we present results of research on universal graphs which are "generic" oligomatic graphs in the sense that most properties of oligomatic graphs can be analyzed by restricting ourselves to universal graphs. Chapters Two to Four deal with the development of heuristics for two types of graph coloring problems. The tabu search heuristic was a central focus of our research. A tabu search iteratively modifies a candidate solution (which becomes the new candidate solution) with the goal of improving it. In such a procedure it is forbidden (tabu) to undo a modification for a certain number iterations. This mechanism allows to escape from local minima. In Chapter Two, we propose general improvements for tabu search based on some new and simple mechanisms (called reactive tabu schemes) to adapt the tabu tenure (which corresponds to the number of iterations a modification stays tabu). We also introduce distance and similarity measures for graph coloring problems which are needed in iterative procedures such as those of the tabu search. In the third chapter, we present the PARTIALCOL heuristic for the graph coloring problem. This method obtains excellent results compared to other similar methods and is able to color the well known DIMACS [JT96] benchmark graph flat300_28_0 optimally with 28 colors. (The best colorings found to date by other researchers use at least 31 colors.) PARTIALCOL uses partial solutions in its search space, which is a little explored way of approaching the graph coloring problem. Most approaches either use colorings and try to minimize the number of colors, or they use improper colorings (having conflicts, i.e. adjacent vertices which may have the same color) and try to minimize the number of conflicts. In the final chapter, we present a weighted version of the graph coloring problem which has applications in batch scheduling and telecommunication problems. We present two different adaptations of tabu search to the weighted graph coloring problem and test several of the reactive tabu schemes presented in Chapter Two. Further, we devise an adaptive memory algorithm AMA inspired by genetic algorithms. A large set of benchmark graphs with different properties is presented. All benchmark graphs with known optima have been solved to optimality by AMA. A key element of this algorithm is its capacity to determine the number k of colors to be used. Most other graph coloring heuristics need this parameter to be supplied by the user. Considering the results obtained on various graphs, we are confident that the methods developed are very efficient.

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit problem. Chapter 1 presents basic definitions of graph theory, such as graph coloring, graph coloring with color-classes of bounded size b, and Hamiltonian circuits and paths. We also present online algorithms and online coloring. Chapter 2 starts with some general remarks about online graph covering with sets of bounded sizes (such as online bounded coloring): we give a simple method for transforming an online covering algorithm into an online bounded covering algorithm, and to derive the performance ratio of the bounded algorithm from the performance ratio of the unbounded algorithm. As will be shown in later chapters, this method often leads to optimal results. Furthermore, some basic preliminary results on online graph covering with sets of bounded size are given: for every graph, the performance ratio is bounded above by 1/2 + b/2 and for b = 2, this bound is optimal. In the second part, online coloring of co-interval graphs is studied. Based on two industrial applications, two different versions of this problem are discussed. In the case where the intervals are presented in increasing order of their left ends, we show that the performance ratio is 1 in the unbounded case and 2 - 1/b in the bounded case. In the case where the intervals may be presented in any order, we show that the performance ratio is at most 3 in the bounded case. Chapter 3 deals with online coloring of permutation and comparability graphs. First, we give a tight analysis of the First-Fit algorithm on bipartite permutation graphs and we show that its performance ratio is O(√n), even for some simple presentation orders. For both classes of graphs, we show that the performance ratio is bounded above by (χ+1)/2 in the unbounded case and that the performance ratio of First-Fit is equal to 1/2 + b/2 in the bounded case. In the second part of this chapter, we study cocoloring of permutation graphs. We show that the performance ratio is n/4 + 1/2 and we give better bounds in some more restricted cocoloring problems. Chapter 4 deals with an application of online coloring: the online Track Assignment Problem. Depending on the assumptions that are made, the Track Assignment Problem can be reduced to coloring permutation or overlap graphs online. We show that when a permutation graph is presented on a latticial plane, from west to east, then the performance ratio is exactly 2 - (min{b,k})-1, where k is the best known upper bound on the bounded chromatic number. We also show that, when a permutation graph is presented on a latticial plan, starting from the origin and growing, simultaneously or not, towards west and east, then the performance ratio is exactly 2 - 1/χ. We also show that online coloring overlap graphs does not have a performance ratio bounded by a constant, even if the overlap graph is bipartite and presented in increasing order of the intervals left ends. In this special case, we show that First-Fit has a tight performance ratio of O(√n). We consider coloring overlap graphs online where the intervals have a bounded size between 1 and a given number M. In this case, we show that the performance ratio can be bounded above by 2√M if M ≤ M0, and by log M (⎡log M / log log M⎤ + 1) if M > M0, M0 being defined by the equation 2√M0 = 3 log(M0). For large values of M, the ratio is O(log2 M / log log M). Chapter 5 is about online coloring of trees, forests and split-graphs. For trees, we show that the performance ratio of online coloring is exactly ½log2(2n) in the unbouded case and at most 1 + ⎣log2(b)⎦/χb in the bounded case. For split-graphs, we show that the performance ratio of online coloring is exactly 1 + 1/χ in the unbounded case and is at most 2 + 1/χb + 3/b in the bounded case. In Chapter 6, we present a class of digraphs: the quasi-adjoint graphs. These are a super class of both the graphs used for a DNA sequencing algorithm in (Blazewicz, Kasprzak, "Computational complexity of isothermic DNA sequencing by hybridization", 2006) and the adjoints. A polynomial recognition algorithm in O(n3), as well as a polynomial algorithm in O(n2 + m2) for finding a Hamiltonian circuit in quasi-adjoint graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a sequence of two consecutive arcs) are discussed.

EPFL2008

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different colors. This thesis deals with some variations of this basic coloring problem which are related to scheduling and discrete tomography. These problems may also be considered as partitioning problems. In Chapter 1 basic definitions of computational complexity and graph theory are presented. An introduction to graph coloring and discrete tomography is given. In the next chapter we discuss two coloring problems in mixed graphs (i.e., graphs having edges and arcs) arising from scheduling. In the first one (strong mixed graph coloring problem) we have to cope with disjunctive constraints (some pairs of jobs cannot be processed simultaneously) as well as with precedence constraints (some pairs of jobs must be executed in a given order). It is known that this problem is NP-complete in mixed bipartite graphs. In this thesis we strengthen this result by proving that for k = 3 colors the strong mixed graph coloring problem is NP-complete even if the mixed graph is planar bipartite with maximum degree 4 and each vertex incident to at least one arc has maximum degree 2 or if the mixed graph is bipartite and has maximum degree 3. Furthermore we show that the problem is polynomially solvable in partial p-trees, for fixed p, as well as in general graphs with k = 2 colors. We also give upper bounds on the strong mixed chromatic number or even its exact value for some classes of graphs. In the second problem (weak mixed graph coloring problem), we allow jobs linked by precedence constraints to be executed at the same time. We show that for k = 3 colors this problem is NP-complete in mixed planar bipartite graphs of maximum degree 4 as well as in mixed bipartite graphs of maximum degree 3. Again, for partial p-trees, p fixed, and for general graphs with k = 2 colors, we prove that the weak mixed graph coloring problem is polynomially solvable. We consider in Chapter 3 the problem of characterizing in an undirected graph G = (V, E) a minimum set R of edges for which maximum matchings M can be found with specific values of p = |M ∩ R|. We obtain partial results for some classes of graphs and show in particular that for odd cacti with triangles only and for forests one can determine in polynomial time whether there exists a minimum set R for which there are maximum matchings M such that p= |R ∩ M|, for p= 0,1, ..., ν(G). The remaining chapters deal with some coloring (or partitioning) problems related to the basic image reconstruction problem in discrete tomography. In Chapter 4 we consider a generalization of the vertex coloring problem associated with the basic image reconstruction problem. We are given an undirected graph and a family of chains covering its vertices. For each chain the number of occurrences of each color is given. We then want to find a coloring respecting these occurrences. We are interested in both, arbitrary and proper colorings and give complexity results. In particular we show that for arbitrary colorings the problem is NP-complete with two colors even if the graph is a tree of maximum degree 3. We also consider the edge coloring version of both problems. Again we present some complexity results. We consider in Chapter 5 some generalized neighborhoods instead of chains. For each vertex x we are given the number of occurrences of each color in its open neighborhood Nd(x) (resp. closed neighborhood Nd+(x)), representing the set of vertices which are at distance d from x (resp. at distance at most d from x). We are interested in arbitrary colorings as well as proper colorings. We present some complexity results and we show in particular that for d = 1 the problems are polynomially solvable in trees using a dynamic programming approach. For the open neighborhood and d = 2 we obtain a polynomial time algorithm for quatrees (i.e. trees where all internal vertices have degree at least 4). We also examine the bounded version of these problems, i.e., instead of the exact number of occurrences of each color we are given upper bounds on these occurrences. In particular we show that the problem for proper colorings is NP-complete in bipartite graphs of maximum degree 3 with four colors and each color appearing at most once in the neighborhood N(x) of each vertex x. This result implies that the L(1,1)-labelling problem is NP-complete in this class of graphs for four colors. Finally in Chapter 6 we consider the edge partitioning version of the basic image reconstruction problem, i.e., we have to partition the edge set of a complete bipartite graph into k subsets such that for each vertex there must be a given number of edges of each set of the partition incident to this vertex. For k = 3 the complexity status is still open. Here we present a new solvable case for k = 3. Then we examine some variations where the union of two subsets E1, E2 has to satisfy some additional constraints as for example it must form a tree or a collection of disjoint chains. In both cases we give necessary and sufficient conditions for a solution to exist. We also consider the case where we have a complete graph instead of a complete bipartite graph. We show that the edge partitioning problem in a complete graph is at least as difficult as in a complete bipartite graph. We also give necessary and sufficient conditions for a solution to exist if E1 ∪ E2 form a tree or if they form a Hamiltonian cycle in the case of a complete graph. Finally we examine for both, complete and complete bipartite graphs, the case where each one of the sets E1 and E2 is structured (two disjoint Hamiltonian chains, two edge disjoint cycles) and present necessary and sufficient conditions.

EPFL2007

Some combinatorial optimization problems in graphs with applications in telecommunications and tomography

David Schindl

The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set problem, and provide some new graph classes, where it can be solved in polynomial time. Those classes are hereditary, i.e. characterized by a list of forbidden induced subgraphs. The algorithms proposed are purely combinatorial. The second chapter is devoted to the study of a problem linked to security purposes in mobile telecommunication networks. The particularity is that there is no central authority guaranteeing security, but it is actually managed by the users themselves. The network is modelled by an oriented graph, whose vertices represent the users, and whose arcs represent public key certificates. The problem is to associate to each vertex a subgraph with some requirements on the size of the subgraphs, the number of times a vertex is taken in a subgraph and the connectivity between any two users as they put their subgraphs together. Constructive heuristics are proposed, bounds on the optimal solution and a tabu search are described and tested. The third chapter is on the problem of reconstructing an image, given its projections in terms of the number of occurrences of each color in each row and each column. The case of two colors is known to be polynomially solvable, it is NP-complete with four or more colors, and the complexity status of the problem with three colors is open. An intermediate case between two and three colors is shown to be solvable in polynomial time. The last two chapters are about graph (vertex-)coloring. In the fourth, we prove a result which brings a large collection of NP-hard subcases, characterized by forbidden induced subgraphs. In the fifth chapter, we approach the problem with the use of linear programming. Links between different formulations are pointed out, and some families of facets are characterized. In the last section, we study a branch and bound algorithm, whose lower bounds are given by the optimal value of the linear relaxation of one of the exposed formulations. A preprocessing procedure is proposed and tested.

EPFL2004