BRICS Basic Research in Computer Science

(1)

B R ICS R S -02-45 J . M. B ysk o v : C h romatic Nu mb er in T ime O (2 . 4023 n )

BRICS

Basic Research in Computer Science

Chromatic Number in Time O(2.4023 ⁿ ) Using Maximal Independent Sets

Jesper Makholm Byskov

BRICS Report Series RS-02-45

ISSN 0909-0878 December 2002

(2)

Copyright c 2002, Jesper Makholm Byskov.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications.

Copies may be obtained by contacting:

BRICS

Department of Computer Science University of Aarhus

Ny Munkegade, building 540 DK–8000 Aarhus C

Denmark

Telephone: +45 8942 3360 Telefax: +45 8942 3255 Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk ftp://ftp.brics.dk

This document in subdirectory RS/02/45/

(3)

Chromatic Number in Time

O(2.4023 ⁿ )

Using Maximal Independent Sets

Jesper Makholm Byskov

BRICS

∗

Department ofComputer Science

UniversityofAarhus, Denmark

jespermn@brics.dk

December, 2002

Abstract

Inthis paperweimprove an algorithm byEppstein (2001) for

nding the chromatic number of a graph. We modify the algo-

rithmslightly, and by using a bound on the number of maximal

independentsets of size

k

^from^our^recent ^paper^(2003), ^we ^prove

thattherunningtimeis

O(2.4023 ⁿ )

^. ^Eppstein's^algorithm^runsⁱⁿ

time

O(2.4150 ⁿ )

^. ^The^space ûsage^for ^bothâlgorithms îs

O(2 ⁿ )

^.

1 Introduction

1.1 Lawler's algorithm

Lawler [Law76] was the rst to give a non-trivial algorithm for nding

thechromaticnumberofagraph. Henotesthatinacolouringofagraph

one of the colour classes can be assumed to be a maximal independent

set (aMIS).Sowecan nd the chromaticnumber

χ(G)

^of ^a^graph

G

^by

the following recursion:

χ(G[S]) =

( 1 + min{χ(G[S \ I ]) | I ∈ I (G[S])}

^if

S 6= ∅

^,

0

^if

S = ∅

^,

∗

BasicResearchin ComputerScience(www.brics.dk),

funded bytheDanishNationalResearchFoundation.

(4)

let

X

^be ân ârray îndexed ^from ⁰^to

2 ⁿ − 1

for

S = 0

^to

2 ⁿ − 1

^do

for all MISs

I

^of

G[S]

^do

X[S] = min(X [S], X[S \ I] + 1)

return X[V]

where

G[S]

^denotes ^the vertex-induced subgraph of

S ⊆ V

^and

I(G)

denotes the set of all maximal independent sets of

G

^. ^Lawler ^does ^not

explicitly give an algorithm. He merely notes that one has to process

all subsets of

S

^before

S

îs ^processed. Îf ^we îndex âll ^subsets ^from ⁰

to

2 ⁿ − 1

^such ^that ^the bit-representation of each index is a bit vector denotingfor eachvertex whether it isinthe set or not, Algorithm1will

ndthe chromaticnumberof

G

^. ^Using^the^bound

3 ^n/3

^on^the ^number^of

maximalindependentsetsofagraph([MM65 ])andthefactthattheycan

be found within a polynomial factor of this bound (see e.g. [TIAS77]),

this has runningtime

O X

S⊆V

|I (G[S])|

!

= O X n

i=0

n i

3 ^i/3

!

= O (1 + 3 ^1/3 ) ⁿ ,

which is

O(2.4423 ⁿ )

^. ^The ^algorithm^uses ^space

O(2 ⁿ )

^to^store

X

^.

1.2 Eppstein's algorithm

Eppstein[Epp01b ]improvesLawler'salgorithm. Lawler'salgorithmcom-

putes

χ(G[S])

^by ^looking ^at ^the ^values ^for ^subsets ^of

S

^. ^Eppstein's ^al-

gorithm also computes a table

X[S]

^for ^all

S ⊆ V

^(indexed ^as ^above),

but every time it reaches a set

S

^, ^it ^updates

X

^for ^all ^supersets ^of

S

forwhichthe value

X[S]

^could potentiallygive better values. More pre- cisely,if

G[S]

^is^a^maximal

k

-colourablesubgraph of

G

^,^it^has^a^maximal

(k − 1)

-colourable subgraph

G[S ⁰ ]

^of ^size ^at ^least

|S ⁰ | ≥ (k − 1)/k · |S|

^,

and

S \ S ⁰

^is ^a ^maximal independent set of

G[V \ S ⁰ ]

^. ^Thus, ^when ^the

chromaticnumber of

G[S ⁰ ]

îs ^computed, ônly^the ^values ôf

G[S ⁰ ∪ I]

^for

allmaximalindependent sets

I

^of ^size ^at^most

|S ⁰ |/χ(G[S ⁰ ])

ⁱⁿ

G[V \ S ⁰ ]

are updated. The algorithmis shown as Algorithm2.

Therstpartofthealgorithmchecks1-and2-colourabilityinpolyno-

mialtimeand3-colourabilityusingthe3-colouringalgorithmof[Epp01a],

with running time

O(1.3289 ⁿ )

^, ôf âll ^subgraphs ôf

G

^. ^The ^second ^part

(5)

let

X

2 ⁿ − 1

for

S = 0

^to

2 ⁿ − 1

^do

if

χ(S) ≤ 3

^then

X[S] = χ(S)

else

X[S] = ∞

for

S = 0

^to

2 ⁿ − 1

^do

if

3 ≤ X[S] < ∞

^then

for all MISs

I

^of

G[V \ S]

^of ^size ^at^most

|S|/X [S]

^do

X[S ∪ I ] = min(X[S ∪ I], X[S] + 1)

return X[V]

runs through

X

^and ^for ^each ^subgraph

G[S]

ît ^nds âll ^maximal înde-

pendentsets

I

^of

G[V \ S]

^of^size^at^most

|S|/X[S]

^and^updates^the^value

of

X[S ∪ I]

^.

It is clear that for any set

S ⊆ V

^,

χ(G[S]) ≤ X[S]

^during ^the ^exe-

cutionof the algorithm,since

X[S]

îs ônly ûpdated ^when ^the âlgorithm

actually nds a colouring with

X[S]

^colours. ^F^or ^every

k

^, ^all ^maximal

k

-colourable subgraphs

G[M ]

^have

X[M ] = k

^, ^since ^they ^have ^so ^for

k ≤ 3

âfter ^the ^rst ^half ôf ^the âlgorithm ^has ^run, ând ^thus ^by înduc-

tion also for larger

k

^, ^by ^the ^argument ^above. ^Since

G

^is ^a ^maximal

χ(G)

-colourablesubgraph ofitself,the algorithmcorrectlycomputes the chromaticnumber of

G

^.

The runningtime of the the rst part of the algorithmis:

X

S⊆V

O(1.3289 ^|S| ) = O X n

i=0

n i

1.3289 ⁱ

! ,

whichis

O(2.3289 ⁿ )

^. ^The^second^part^might^beêxecuted ^forâlmostâll

S

^,

butsince

X[S] ≥ 3

^, ^only^maximalindependentsets ofsize atmost

|S|/3

in

G[V \ S]

^are considered. Using a lemma, that states that a graph canhave atmost

3 ^4k−n 4 ^n−3k

^maximalindependentsets of size atmost

k

and that they can be found within a polynomial factor of this bound,

(6)

Eppsteingets that the running time of the second part isat most

X

S⊆V

O(3 4(|S|/3)−(n−|S|) 4 (n−|S|)−3(|S|/3) ) = O 4 3

_{n n} X

i=0

n i

3 ^7/3 4 ²

_i !

= O 4

3 + 3 ^4/3 4

_n ! ,

which equals

O(2.4151 ⁿ )

^, ^so ^this îs ^the ^running ^time ôf ^the âlgorithm.

The space usageis

O(2 ⁿ )

^.

2 Results

We show how to improve the algorithm of Eppstein to run in time

O(2.4023 ⁿ )

^. ^The^rst ^partôf^the âlgorithmsâre ^the^same, ^namely^mark-

ing all 3-colourable subgraphs of the graph in a bit vector. Then our

algorithmndsallmaximalindependent sets

I

ôf ^the^graphând ^forêach

checks 3-colourabilityofallsubgraphs

S

^of

G[V \ I]

^,^by^lookingⁱⁿ^the^bit

vector. If they are 3-colourable,

G[S ∪ I ]

^is 4-colourable. This will nd allmaximal4-colourablesubgraphs(andmaybesome thatarenot maxi-

mal). Usingthebound

b ⁿ _k c (bn/kc+1)k−n (b ⁿ _k c + 1) ^n−bn/kck

^on^the ^number^of

maximalindependent sets of size

k

^from^our ^paper^{[Bys03 ],} ^and ^the ^fact

thatthey can befound within apolynomial factor ofthis bound,we get

that the runningtime for ndingall maximal4-colourable subgraphs is:

X n k=1

O(|I k (G)| · 2 ^n−k ) = O

b ⁿ ₅ c

X

k=1

5 ^6k−n 6 ^n−5k 2 ^n−k + X n k=b ⁿ ₅ c+1

4 ^5k−n 5 ^n−4k 2 ^n−k

!

= O(80 ^n/5 ),

which is

O(2.4023 ⁿ )

^,^and ^where

I k (G)

^denotes ^the ^set ôf âll^maximal în-

dependent sets of

G

^of ^size

k

^. ^Then ^our ^algorithm^performs ^the ^second

step of Eppstein's algorithm, but it only needs to consider maximal in-

dependent sets of size at most

|S|/4

ând ûsing ôur împroved ^bound ôn

the number of these, weget that the runningtime is:

X

S⊆V

O(4 5(|S|/4)−(n−|S|) 5 (n−|S|)−4(|S|/4) ) = O 5 4

_{n n} X

i=0

n i

4 ^9/4 5 ²

_i !

= O 5

4 + 4 ^5/4 5

_n !

,

(7)

let

X

2 ⁿ − 1

for

S = 0

^to

2 ⁿ − 1

^do

if

χ(S) ≤ 3

^then

X[S] = χ(S)

else

X[S] = ∞

for all MISs

I

ⁱⁿ

G

^do

for all subsets

S

^of

V \ I

^do

if

X[S] = 3

^then

X[S ∪ I ] = min(X[S ∪ I], 4)

for

S = 0

^to

2 ⁿ − 1

^do

if

4 ≤ X[S] < ∞

^then

for all MISs of

G[V \ S]

^of ^size ^at^most

|S|/X [S]

^do

X[S ∪ I ] = min(X[S ∪ I], X[S] + 1)

return X[V]

whichis

O(2.3814 ⁿ )

^. ^Theâlgorithmîs^shownâsÂlgorithm^3. Ît^stillûses

space

O(2 ⁿ )

^.

Remark. In[Bys03]wealsoshowhowtomarkall3-colourablesubgraphs

of a graph in a bit vector in time

O(2.2680 ⁿ )

^, ^by ^nding ^all ^maximal

independentsetsandforeachndallmaximalbipartitesubgraphsofthe

remaininggraph(whichcanbedonebyndingmaximalindependentsets

twice). Thisimprovestherunningtimeoftherststepandalsosimplies

the algorithmas it does not use the 3-colouring algorithm of Eppstein,

but insteaduses maximalindependent sets.

References

[Bys03] J.M.Byskov. Algorithmsfor

k

^-colouring^and^nding^maximal

independent sets. In Proc. 14th Symp. Discrete Algorithms.

ACM and SIAM, Jan. 2003. To appear.

[Epp01a] D. Eppstein. Improved algorithms for 3-coloring, 3-edge-

coloring,and constraintsatisfaction. InProc. 12thSymp. Dis-

crete Algorithms, pages 329337.ACM and SIAM, Jan. 2001.

URLhttp://arXiv.org/abs/cs. DS/0 0090 06.

(8)

graph coloring. In F. Dehne, J.-R. Sack and R. Tamassia,

editors, Proc. 7th Worksh. Algorithms and Data Structures,

volume2125ofLectureNotesin ComputerScience,pages462

470. Springer-Verlag, Aug. 2001. URL http://arXiv.org/

abs/cs.DS/0011009.

[Law76] E.L.Lawler. Anote onthecomplexityofthe chromaticnum-

berproblem. Inf. Process. Lett., 5(3):6667,Aug. 1976.

[MM65] J.W.MoonandL.Moser. Oncliquesingraphs.IsraelJournal

of Mathematics, 3:2328,1965.

[TIAS77] S.Tsukiyama,M.Ide,H.Ariyoshi andI.Shirakawa. Anewal-

gorithmforgeneratingallthemaximalindependentsets.SIAM

J.Comput., 6(3):505517,Sept. 1977.

(9)

Recent BRICS Report Series Publications

RS-02-45 Jesper Makholm Byskov. Chromatic Number in Time O(2.4023 ⁿ ) Using Maximal Independent Sets. December 2002.

6 pp.

RS-02-44 Zoltán ´ Esik and Zoltán L. Németh. Higher Dimensional Au- tomata. November 2002. 32 pp. A preliminary version appears under the title Automata on Series-Parallel Biposets in Kuich, Rozenberg and Salomaa, editors, 5th International Conference, Developments in Language Theory, DLT ’01 Revised Papers, LNCS 2295, 2001, pages 217–227. This report supersedes the earlier BRICS report RS-01-24.

RS-02-43 Mikkel Christiansen and Emmanuel Fleury. Using IDDs for Packet Filtering. October 2002. 25 pp.

RS-02-42 Luca Aceto, Jens A. Hansen, Anna Ing´olfsd´ottir, Jacob Johnsen, and John Knudsen. Checking Consistency of Pedi- gree Information is NP-complete (Preliminary Report). October 2002. 16 pp.

RS-02-41 Stephen L. Bloom and Zolt´an ´ Esik. Axiomatizing Omega and Omega-op Powers of Words. October 2002. 16 pp.

RS-02-40 Luca Aceto, Willem Jan Fokkink, and Anna Ing ´olfsd´ottir. A Note on an Expressiveness Hierarchy for Multi-exit Iteration.

September 2002. 8 pp.

RS-02-39 Stephen L. Bloom and Zolt´an ´ Esik. Some Remarks on Regular Words. September 2002. 27 pp.

RS-02-38 Daniele Varacca. The Powerdomain of Indexed Valuations.

September 2002. 54 pp. Short version appears in Plotkin, ed- itor, Seventeenth Annual IEEE Symposium on Logic in Com- puter Science, LICS ’02 Proceedings, 2002, pages 299–308.

RS-02-37 Mads Sig Ager, Olivier Danvy, and Mayer Goldberg. A Sym- metric Approach to Compilation and Decompilation. August 2002. To appear in Neil Jones’s Festschrift.

BRICS Basic Research in Computer Science

B R ICS R S -02-45 J . M. B ysk o v : C h romatic Nu mb er in T ime O (2 . 4023 n )

BRICS

Basic Research in Computer Science

Chromatic Number in Time O(2.4023 n ) Using Maximal Independent Sets

Jesper Makholm Byskov

BRICS Report Series RS-02-45

ISSN 0909-0878 December 2002

Copyright c 2002, Jesper Makholm Byskov.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications.

Copies may be obtained by contacting:

BRICS

Department of Computer Science University of Aarhus

Ny Munkegade, building 540 DK–8000 Aarhus C

Denmark

Telephone: +45 8942 3360 Telefax: +45 8942 3255 Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk ftp://ftp.brics.dk

This document in subdirectory RS/02/45/

O(2.4023 n )

∗

k

O(2.4023 n )

O(2.4150 n )

O(2 n )

χ(G)

G

χ(G[S]) =

( 1 + min{χ(G[S \ I ]) | I ∈ I (G[S])}

S 6= ∅

0

S = ∅

∗

X

2 n − 1

S = 0

2 n − 1

I

G[S]

X[S] = min(X [S], X[S \ I] + 1)

G[S]

S ⊆ V

I(G)

G

S

S

2 n − 1

G

3 n/3

O X

S⊆V

|I (G[S])|

!

= O X n

i=0

n i

3 i/3

!

= O (1 + 3 1/3 ) n ,

O(2.4423 n )

O(2 n )

X

χ(G[S])

S

X[S]

S ⊆ V

S

X

S

X[S]

G[S]

k

G

(k − 1)

G[S 0 ]

|S 0 | ≥ (k − 1)/k · |S|

S \ S 0

G[V \ S 0 ]

Chromatic Number in Time O(2.4023 ⁿ ) Using Maximal Independent Sets

O(2.4023 ⁿ )

O(2.4023 ⁿ )

O(2.4150 ⁿ )

O(2 ⁿ )

2 ⁿ − 1

2 ⁿ − 1

2 ⁿ − 1

3 ^n/3

3 ^i/3

= O (1 + 3 ^1/3 ) ⁿ ,

O(2.4423 ⁿ )

O(2 ⁿ )

G[S ⁰ ]

|S ⁰ | ≥ (k − 1)/k · |S|

S \ S ⁰

G[V \ S ⁰ ]

G[S ⁰ ]

G[S ⁰ ∪ I]

|S ⁰ |/χ(G[S ⁰ ])

G[V \ S ⁰ ]

O(1.3289 ⁿ )

2 ⁿ − 1

2 ⁿ − 1

2 ⁿ − 1

O(1.3289 ^|S| ) = O X n

1.3289 ⁱ

O(2.3289 ⁿ )

3 ^4k−n 4 ^n−3k

_{n n} X

3 ^7/3 4 ²

_i !

3 + 3 ^4/3 4

_n ! ,

O(2.4151 ⁿ )

O(2 ⁿ )

O(2.4023 ⁿ )