Algorithmic Aspects of Graph Coloring
Lead Research Organisation:
Durham University
Department Name: Engineering and Computing Sciences
Abstract
We consider a variety of practical situations in which attributes (wavelengths, frequencies, time slots, machines) have to be allocated to conflicting objects (optical data streams, transmitters, traffic streams, jobs) in such a way that no pair of conflicting objects receives the same attribute. We model such situations as graph coloring problems. A graph is given by a set of vertices that represent the objects and a set of unordered pairs of vertices, called edges, representing the conflicts between pairs of objects. Graph coloring involves the labeling of the vertices of some given graph by integers called colors such that no two adjacent vertices receive the same color. In many applications the objective is to minimize the number of colors. Graph coloring has been a popular research topic since its introduction as a map coloring problem more than 150 years ago. Some reasons for this are its appealingly simple definition, its large variety of open problems, and its many application areas. Whenever conflicting situations between pairs of objects can be modeled by graphs, and one is looking for a partition of the set of objects in subsets of mutually non-conflicting objects, this can be viewed as a graph coloring problem. This holds for classical settings such as neighboring countries (map coloring) or interfering jobs on machines (job scheduling), as well as for more recent settings like colliding data streams in optical networks (wavelength assignment), colliding traffic streams (time slot allocation) or interfering transmitters and receivers for broadcasting, mobile phones and sensors (frequency assignment), to name just a few. Note that even the nowadays so immensely popular pass-time of Sudokus comes down to coloring a (partially precolored) graph on 81 vertices (representing the 81 squares of the Sudoku) with 9 colors (the integers 1 to 9).In the classical setting the coloring is done off-line in the sense that the whole graph is known and it does not change over time. Many variants on this simple off-line graph coloring concept have been defined and studied, mainly due to additional restrictions on the coloring. We illustrate this by considering the general framework for coloring problems related to frequency assignment. In this application area graphs are used to model the topology and mutual interference between transmitters (receivers, base stations): the vertices of the graph represent the transmitters; two vertices are adjacent in the graph if the corresponding transmitters are so close (or so strong) that they are likely to interfere if they broadcast on the same or `similar' frequency channels. The problem in practice is to assign the frequency channels to the transmitters in such a way that interference is kept at an `acceptable level'. In many technological applications off-line coloring is not a suitable concept because complete information on the graph one has to color is not known beforehand, e.g. if jobs come in one-by-one and have to be scheduled on machines right away and rescheduling is not possible. In this case one has to consider another variant of coloring, namely on-line graph coloring. In this setting the graph is presented vertex by vertex, and a vertex must irrevocably be assigned a color as it comes in, i.e. the choice of color is only based on the knowledge of the subgraph that has been revealed so far. In general, minimizing the number of colors is an NP-hard problem (it is even more problematic in the on-line setting) . This means that most likely there is no polynomial time ( fast ) algorithm for this problem (an algorithm can be seen as a set of instructions for solving a problem). However, coloring problems occuring in specific situations with extra restrictions might have a different time complexity. Therefore, we try to design and analyse algorithms that solve graph coloring problems both in the on- and off-line setting for several variants as described in our proposal.
Organisations
Publications
Belmonte R
(2013)
Detecting Fixed Patterns in Chordal Graphs in Polynomial Time
in Algorithmica
Belmonte R
(2015)
The Price of Connectivity for Feedback Vertex Set
Belmonte R
(2014)
Parameterized complexity of three edge contraction problems with degree constraints
in Acta Informatica
Belmonte R
(2012)
Combinatorial Optimization and Applications
Belmonte R
(2017)
The price of connectivity for feedback vertex set
in Discrete Applied Mathematics
Belmonte R
(2011)
Algorithms and Computation
Belmonte R
(2013)
Parameterized and Exact Computation
Belmonte R
(2013)
Characterizing graphs of small carving-width
in Discrete Applied Mathematics
Biró P
(2014)
Solutions for the stable roommates problem with payments
in Theoretical Computer Science
Biró P
(2011)
Computing solutions for matching games
in International Journal of Game Theory
Bodlaender H
(2011)
Parameterized Complexity of the Spanning Tree Congestion Problem
in Algorithmica
Bonamy M
(2012)
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
in Journal of Combinatorial Optimization
Bousquet N
(2013)
Parameterized Domination in Circle Graphs
in Theory of Computing Systems
Broersma H
(2013)
Three complexity results on coloring P k -free graphs
in European Journal of Combinatorics
Broersma H
(2012)
Updating the complexity status of coloring graphs without a fixed induced linear forest
in Theoretical Computer Science
Broersma H
(2009)
Combinatorial Algorithms
Broersma H
(2012)
Determining the chromatic number of triangle-free 2 P 3 -free graphs in polynomial time
in Theoretical Computer Science
Broersma H
(2014)
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
in Journal of Graph Theory
Chalopin J
(2014)
Packing bipartite graphs with covers of complete bipartite graphs
in Discrete Applied Mathematics
Chalopin J
(2011)
Graph labelings derived from models in distributed computing: A complete complexity classification
in Networks
Chalopin J
(2010)
Algorithms and Complexity
Chaplick S
(2013)
Fundamentals of Computation Theory
Chaplick S
(2015)
Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
in Theoretical Computer Science
Cochefert M
(2018)
Computing square roots of graphs with low maximum degree
in Discrete Applied Mathematics
Cochefert M
(2013)
Graph-Theoretic Concepts in Computer Science
Cochefert M
(2014)
Parameterized Algorithms for Finding Square Roots
in Algorithmica
Couturier J
(2012)
On the parameterized complexity of coloring graphs in the absence of a linear forest
in Journal of Discrete Algorithms
Couturier J
(2011)
Graph-Theoretic Concepts in Computer Science
Couturier J
(2012)
Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
in Theory of Computing Systems
Couturier J
(2013)
List Coloring in the Absence of a Linear Forest
in Algorithmica
Dabrowski K
(2014)
Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
Dabrowski K
(2016)
Classifying the clique-width of H -free bipartite graphs
in Discrete Applied Mathematics
Dabrowski K
(2014)
Computing and Combinatorics
Dabrowski K
(2014)
Colouring of graphs with Ramsey-type forbidden subgraphs
in Theoretical Computer Science
Dabrowski K
(2014)
Classifying the Clique-Width of $H$-Free Bipartite Graphs
Dabrowski K
(2016)
Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
in The Computer Journal
Dabrowski K
(2013)
Graph-Theoretic Concepts in Computer Science
Dragan F
(2011)
Approximation of minimum weight spanners for sparse graphs
in Theoretical Computer Science
Dragan F
(2011)
Spanners in sparse graphs
in Journal of Computer and System Sciences
Feghali C
(2015)
A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
in Journal of Graph Theory
Feghali C
(2015)
Kempe Equivalence of Colourings of Cubic Graphs
in Electronic Notes in Discrete Mathematics
Fiala J
(2012)
Distance three labelings of trees
in Discrete Applied Mathematics
Fiala J
(2012)
Detecting induced star-like minors in polynomial time
in Journal of Discrete Algorithms
Fiala J
(2013)
A note on contracting claw-free graphs
in Discrete Mathematics & Theoretical Computer Science
Fiala J.
(2013)
A note on contracting claw-free graphs
in Discrete Mathematics and Theoretical Computer Science
Fiala Jiri
(2013)
A Note on Contracting Claw-Free Graphs
in DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
Fomin F
(2011)
Contraction obstructions for treewidth
in Journal of Combinatorial Theory, Series B
Fomin F
(2011)
Cops and Robber Game Without Recharging
in Theory of Computing Systems
Description | The graph colouring problem is that of labeling the nodes of some network (graph) by the smallest number of integers called colours such that no two adjacent nodes are identically coloured. Graph colouring is one of the most important concepts in Mathematics and Computer Science and has many applications, such as map colouring, job or timetable scheduling, colliding data or traffic streams, frequency assignment and pattern matching: whenever conflicting situations between pairs of objects can be modeled by graphs, and one is looking for a partition of the set of objects in subsets of mutually non-conflicting objects, this can be viewed as a graph colouring problem. Graph Colouring is known to be computationally hard for general inputs. As such it is natural to restrict the input to some special graph class to increase our understanding on the kind of graph properties that causes the intractability. Hence, in our project we designed efficient algorithms that solve graph colouring for special classes of graphs (for instance, those that can be characterized by some forbidden subgraph) or showed that such algorithms do not exist for certain graph classes (under reasonable computational complexity assumptions). We also considered closely related and more general concepts such as precolouring extensions, list colourings and graph homomorphisms in order to fully exploit our new techniques. In a separate thread, we considered the on-line setting of graph colouring. In this setting the input graph is presented node by node, and a node must irrevocably be assigned a colour as it comes in, that is, the choice of colour is only based on the knowledge of the subgraph that has been revealed to the algorithm so far. In particular we studied this setting for so-called ecological colourings requiring that every pair of nodes that have the same set of colours in their neighbourhood are coloured alike. This type of graph colouring has applications in social network theory, where one may want to determine patterns of relationships amongst actors in a certain society. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further nodes, added to G one at a time, be coloured so that at each stage the current graph is ecologically coloured? If the answer is yes then we call the pair (G,c) ecologically online extendible. By generalizing the well-known First-Fit algorithm (which allocates the first available colour to a node) we were able to characterize when a pair (G,c) is ecologically online extendible. Moreover, we also gave an efficient algorithm for solving this problem. Finally, the following should be noted. Before we could obtain our results, we were often required to perform a deep analysis into the graph structure. As an important side effect, this led to a number of new graph structural results, which may be of independent interest (in fact we already used some of these results to obtain efficient algorithms for other graph-theoretic problems as well). |
Exploitation Route | We have written a survey paper on graph colouring. This paper is currently under journal review but publicly available (see arXiv:1407.1482). At the moment various teams of researchers are working on these specific problems in an attempt to narrow the gap between polynomial-time solvability and intractibility (see, for instance, arXiv:1310.0340, arXiv:1409.5164, arXiv:1407.2487 and arXiv:1410.0040). |
Sectors | Digital/Communication/Information Technologies (including Software) |
Description | Algorithmic Aspects of On-line Graph Coloring |
Amount | £10,600 (GBP) |
Organisation | The Royal Society |
Sector | Charity/Non Profit |
Country | United Kingdom |
Start | 10/2009 |
End | 09/2011 |
Description | Research Project Grant |
Amount | £187,316 (GBP) |
Funding ID | RPG-2016-258 |
Organisation | The Leverhulme Trust |
Sector | Charity/Non Profit |
Country | United Kingdom |
Start | 10/2016 |
End | 12/2019 |