• Ingen resultater fundet

# BRICS Basic Research in Computer Science

N/A
N/A
Info
Protected

Del "BRICS Basic Research in Computer Science"

Copied!
9
0
0

Hele teksten

(1)

## BRICS

(2)

### This document in subdirectory RS/02/45/

(3)

Chromatic Number in Time

### O(2.4023n )

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

fromourrecent paper(2003), we prove

thattherunningtimeis

### O(2.4023n )

. Eppstein'salgorithmrunsin

time

### O(2.4150n )

. Thespace usagefor bothalgorithms is

### O(2n )

.

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

of agraph

### G

by

the following recursion:

if

,

if

,

### ∗

BasicResearchin ComputerScience(www.brics.dk),

funded bytheDanishNationalResearchFoundation.

(4)

let

### X

be an array indexed from 0to

for

to

do

for all MISs

of

do

return X[V]

where

### G[S]

denotes the vertex-induced subgraph of

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

before

### S

is processed. If we index all subsets from 0

to

### 2 n− 1

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

ndthe chromaticnumberof

. Usingthebound

### 3 n/3

onthe numberof

maximalindependentsetsofagraph([MM65 ])andthefactthattheycan

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

this has runningtime

which is

### O(2.4423n )

. The algorithmuses space

tostore

### 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

for all

### S⊆V

(indexed as above),

but every time it reaches a set

### X

for all supersets of

### S

forwhichthe value

### X[S]

could potentiallygive better values. More pre- cisely,if

isamaximal

### k

-colourablesubgraph of

,ithasamaximal

### (k − 1)

-colourable subgraph

of size at least

,

and

### S\S0

is a maximal independent set of

### G[V\S0 ]

. Thus, when the

chromaticnumber of

### G[S0 ]

is computed, onlythe values of

### G[S0∪I]

for

allmaximalindependent sets

of size atmost

in

### G[V\S0 ]

are updated. The algorithmis shown as Algorithm2.

Therstpartofthealgorithmchecks1-and2-colourabilityinpolyno-

mialtimeand3-colourabilityusingthe3-colouringalgorithmof[Epp01a],

with running time

### O(1.3289n )

, of all subgraphs of

### G

. The second part

(5)

let

### X

be an array indexed from 0to

for

to

do

if

then

else

for

to

do

if

then

for all MISs

of

of size atmost

do

return X[V]

runs through

### X

and for each subgraph

### G[S]

it nds all maximal inde-

pendentsets

of

ofsizeatmost

of

### X[S∪I]

.

It is clear that for any set

,

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

during the exe-

cutionof the algorithm,since

### X[S]

is only updated when the algorithm

actually nds a colouring with

### X[S]

colours. For every

, all maximal

### k

-colourable subgraphs

have

### X[M ] = k

, since they have so for

### k≤ 3

after the rst half of the algorithm has run, and thus by induc-

tion also for larger

### k

, by the argument above. Since

is a maximal

### χ(G)

-colourablesubgraph ofitself,the algorithmcorrectlycomputes the chromaticnumber of

### G

.

The runningtime of the the rst part of the algorithmis:

whichis

### O(2.3289n )

. Thesecondpartmightbeexecuted foralmostall

,

butsince

### X[S]≥ 3

, onlymaximalindependentsets ofsize atmost

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

which equals

### O(2.4151n )

, so this is the running time of the algorithm.

The space usageis

### O(2n )

.

2 Results

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

### O(2.4023n )

. Therst partofthe algorithmsare thesame, namelymark-

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

algorithmndsallmaximalindependent sets

### I

of thegraphand foreach

checks 3-colourabilityofallsubgraphs

of

### G[V\I]

,bylookinginthebit

vector. If they are 3-colourable,

### G[S∪I ]

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

mal). Usingthebound

### bnkc (bn/kc+1)k−n (b nkc + 1) n−bn/kck

onthe numberof

maximalindependent sets of size

### k

fromour paper[Bys03 ], and the fact

thatthey can befound within apolynomial factor ofthis bound,we get

that the runningtime for ndingall maximal4-colourable subgraphs is:

which is

,and where

### Ik (G)

denotes the set of allmaximal in-

dependent sets of

of size

### k

. Then our algorithmperforms the second

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

dependent sets of size at most

### |S|/4

and using our improved bound on

the number of these, weget that the runningtime is:

(7)

let

### X

be an array indexed from 0to

for

to

do

if

then

else

for all MISs

in

do

for all subsets

of

do

if

then

for

to

do

if

then

for all MISs of

of size atmost

do

return X[V]

whichis

### O(2.3814n )

. ThealgorithmisshownasAlgorithm3. Itstilluses

space

### O(2n )

.

Remark. In[Bys03]wealsoshowhowtomarkall3-colourablesubgraphs

of a graph in a bit vector in time

### O(2.2680n )

, by nding all maximal

independentsetsandforeachndallmaximalbipartitesubgraphsofthe

remaininggraph(whichcanbedonebyndingmaximalindependentsets

twice). Thisimprovestherunningtimeoftherststepandalsosimplies

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

References

[Bys03] J.M.Byskov. Algorithmsfor

### k

-colouringandndingmaximal

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)

### 40.

Referencer

RELATEREDE DOKUMENTER

This gives a cleaner semantics to the restriction phenomenon, and further- more avoids the state-space explosions mentioned above. According to [28], we can guarantee that the

of the expressive completeness of this property language with respect to tests. More precisely, we study whether all properties that are testable can

With this relaxation we have been able to define complexity in this model using restricted classes of real numbers and functions.. Interval arithmetic [7], can be used as the

We have presented a wavelet based 3D compression scheme for very large volume data supporting fast random access to individual voxels within the volume. Experiments on the CT data

We give an algorithm list- ing the maximal independent sets in a graph in time proportional to these bounds (ignoring a polynomial factor), and we use this algorithm to

for = 0 is to store a subset of the keys in S and corresponding associated information in a data structure of m bits, trying to optimize the sum of weights.. of

We are able to show a linear (exactly m) upper bound for the monotone span program size of a function on m variables, that is known to have ((m=log m) 3 = 2 ) monotone

Universal families of hash functions [1], widely used in various areas of computer science (data structures, derandomization, cryptology), have the property, among other things,

In [1] we studied the equational theory of the max-plus algebra of the natural numbers N ∨ = (N, ∨, + , 0), and proved that not only its equational theory is not finitely based,

We show that the conjecture is true for every digraph which possesses a quasi-kernel of cardinality at most two and every kernel-perfect digraph, i.e., a digraph for which every

Notions of Σ-definable sets or relations generalise those of computable enumerable sets of natural numbers, and play a leading role in the spec- ification theory that is used in

The for-loop in lines 12-19 is performed n times, and the while-loop in lines 14-19 is performed at most 2( n − 3) times for each edge, since each iteration considers one

For example, labelled asyn- chronous transition systems arising from finite labelled 1-safe Petri nets form a proper subclass of the class of all finite coherent

A main point in this paper is that a fixed structure with random properties (the expander graph) can be used to move random choices from the data structure itself to the

The main purpose of this paper is to show that the techniques developed by Milner in 15, 17] can be adapted to provide a complete axiomatization of the notion of timed

§ 5, we present an abstract approach to operational preorders based on the notion of a test suite.. In § 6, this approach is merged with the bial- gebraic framework to yield a

When the intermediate specifi- cations can be kept small using heuristics for minimization, the state explosion problem is avoided and there are already promising experimental

An observed test run is a timed trace consisting of an alternating sequence of (input or output) actions and time delays. We use the term on-the-fly to describe a test generation

Our graph specications are based on combining the full M2L in form of a backbone formula for specifying ordinary edges together with a special M2L syntax, called edge constraints ,

This yields a simple proof that symmetric functions have logarithmic circuit depth.. They want to find an element that is in one set but not in the other, using as little

As an application of the main theorem, it is shown that the language of Basic Process Algebra (over a singleton set of actions), with or without the empty process, has no

In this paper we represent continuous data types by suitable structures without the equality test.. This is motivated by the following

We have seen that displacements, together with universal hash functions, form the basis of very efficient (minimal) perfect hashing schemes.. The efficiency of evaluation is very