1Introduction HansL.Bodlaender Anoteondominotreewidth

A note on domino treewidth

Hans L. Bodlaender

Department of Computer Science, University of Utrecht, P.O.Box 80.089, 3508 TB Utrecht, the Netherlands. Email:

[email protected].

received August 11, 1998, revised May 14, 1999, accepted May 27, 1999.

In [DO95], Ding and Oporowski proved that for every , and , there exists a constant , such that every graph with treewidth at most and maximum degree at most has domino treewidth at most . This note gives a new simple proof of this fact, with a better bound for , namely .

It is also shown that a lower bound of holds: there are graphs with domino treewidth at least ^!"#, treewidth at most , and maximum degree at most , for many values and . The domino treewidth of a tree is at most its maximum degree.

Keywords: treewidth, domino treewidth, graph algorithms, tree decompositions

1 Introduction

In [DO95], Ding and Oporowski proved that for every ^$ and ^% , every graph ^{& '} ( )+*-,". with treewidth at most ^$ and with maximum degree at most ^% has a tree decomposition of width at most

/10!2

(435656$78%:96*<;>=:556%69., such that every vertex^?A@B) belongs to at most two of the sets associated to the nodes in the tree decomposition. Such a tree decomposition was called a domino tree decomposition by Bodlaender and Engelfriet in [BE97], where they independently gave a similar result, but with a more complicated proof and with a much higher constant, which was exponential, both in^$ and in^% .

In this note, a new and easy to understand proof for the result is given. Additionally, the constant factor arising from the proof given here is smaller: it is shown that graphs with treewidth at most^$ and maximum degree at most^% have domino treewidth at most ( C6$ED#F!.G%H( %IDKJL.NMOJ .

The proof uses amongst others a technique from [BGHK95] (inspired by a technique from [RS95]), and some other ideas. The proof is given in Section 3.

In Section 4, it is shown that a lower bound of^{PQ( $%R.} holds: there are graphs with domino treewidth at least ^S

S7

$T%UMOJ , treewidth at most^$ , and maximum degree at most^% , for many values^$ and^% .

Some final remarks are made in Section 5, and it is shown that the domino treewidth of a tree is at most its maximum degree.

V

This research was partially supported by ESPRIT Long Term Research Project 20244 (project ALCOM IT: Algorithms and Complexity in Information Technology).

1365–8050 c

W

1999 Maison de l’Informatique et des Math´ematiques Discr`etes (MIMD), Paris, France

2 Definitions and Preliminary Results

Definition. A tree decomposition of a graph&X'X()Y*<,Z. is a pair (\[^]`_baTcd@feTg:*Ghi'X( ej*<kU.G. with

[]`_lacY@mejg a collection of subsets of⁾ , andhn'o( ej*<kU. a tree, such that

pAq

_4rs ] _ 't)

p for all edges(4?H*-uI.@m, there is an^c+@ve with^{?w*Gux@v] _}

p for all^c*zy*$d@{e : if^y is on the path from^c to^$ in^h , then^{] _j| ]`}Z~O]Z} .

The width of a tree decomposition (\[]`_€a!cU@AeTg:*Gh'i(4eH*-kU.G. is<sup>/`0>2 _4rs‚a</sup>]1_<a:MtJ . The treewidth of a graph&x'ƒ( )+*-,Z. is the minimum width over all tree decompositions of^& .

In some cases,^h will be considered a rooted tree; a specific node of^h is considered to be the root. A tree decomposition^{( „v*-hI.} with^h a rooted tree is called a rooted tree decomposition. For a node^cI@e , we call the set^{] _} the bag of^c.

Definition. A tree decomposition(\[^]`_YaLc…@ejg6*-hB'†(4eH*-kU.-. of&†'†( )+*-,Z. is a domino tree decom- position, if for each vertex<sup>?d@)</sup> , there are at most two nodes<sup>c‚@‡e</sup> with<sup>?{@]`_</sup>. The domino treewidth of a graph&o'f()Y*<,Z. is the minimum width over all domino tree decompositions of^& .

The open neighbourhood of a set of vertices^ˆ‰~O) in a graph&f'o()Y*<,Z. is

Š

(ˆf.+'B[^?‹@)BMŒˆa^ŽRuf@ˆ‰[?w*GuEgU@v,1g

For a graph&o'f()Y*<,Z., and^ˆ~K) , the subgraph of^& , induced by^ˆ is denoted as

&`ˆ’‘'f(ˆŒ*[6[?w*GuEgU@v,“a?w*Guf@mˆ“gL.

Lemma 2.1 LethK'ƒ(4eH*-kU. be a tree. Let^”

S

~Ae . Then there exists a set^”

7

~#e with

p

a•”

7

a–#—™˜6a•”

S

a>MOJ .

p ” S

~’”

7

.

p Every subtree of^h"eEMA”

7 ‘ is adjacent to at most two nodes in^”

7

.

Proof: Choose an arbitrary root^š in^h . Let^”

7

'x”

Sl›

[y`@ve`a-y is the lowest common ancestor of two nodes in^”

S g . We claim that this set^”

7

fulfils the conditions. Clearly,^”

S

~t”

7

. Let^hIœ be a subtree of^hZeQM”

7 ‘. If^czžE@”

7

is adjacent to a node in^hbœ, then there are two cases:

p cž is an ancestor of a node in^hbœ. Then^cž is the unique parent of the root of^hIœ.

p cž is a child of a node in^hbœ. We claim that there can be only one node fulfilling this case (for this tree ^hbœ): suppose^{cž @”}

7

and^c

S

@“”

7

are children of nodes in ^hbœ. Then, the lowest common ancestor^c

7

of^cž and^c

S

belongs to^hbœ. However,^cž and^c

S

belong to^”

S

or are ancestor of a node in ^”

S

. So,^c

7

is the lowest common ancestor of two nodes in ^”

S

, which is a contraction with the observation that it belongs to^hbœ.

As for^hbœ, each case can appear only once,^hbœ is adjacent to at most two nodes in^”

7

. To show that ^aŸ”

7

a –f—Z˜ja•”

S

a6MnJ , build a tree^¡ in the following way: ^”

7

is the set of nodes in^¡ . If

yv@”

7

has an ancestor that also belongs to^”

7

, then take an edge from^y to the closest ancestor that also belongs to ^”

7

. One can observe that^¡ is indeed a tree. Every node^ym@A”

7

M#”

S

must have at least two children. So ^¡ is a tree with at most ^aŸ”

S a leaves, and without nodes with one child. A well know fact about trees tells us that^¡ has at most^—HaŸ”

S

a>MOJ nodes, hence^a•”

7

a–O—™˜:a•”

S

a>MOJ .^¢

Lemma 2.2 Let (£[]`_IaTcd@oejg6*-h¤'¥( ej*<kU.G. be a tree decomposition of &¥'¦( )+*-,".. Let ^{ˆ ~§)} ,

aˆ¨a'nš . Let^©EªOš .

1. There exists a set of «š¬( ©™DfJL.z­ nodes ^”

S

~†e , such that each connected component of^&`)M

q 

r6®¯

]`_4‘ contains at most^© vertices from^ˆ .

2. There exists a set of — «š¬(©EDJ^.\­°MfJ nodes ^”

7

~¤e , such that each connected component ^± of^{&`)†M q}  r6®²

] _‘ contains at most^© vertices from^ˆ , and for each connected component of

&`)fM q  r6®²

] _‘ there are nodes^c

S

*-c

7

@³”

7

, such that every vertex^? that is adjacent to a vertex in^± belongs to^±

› ] _´¯

› ] _² .

Proof: 1. First, observe that for any^”’~†e ,^{&`)M q}  r6®

]`_‘ consists of a number of connected components, such that for any connected component<sup>±</sup> of<sup>&`)xM q</sup>  r6®

]`_‘, we have a subtree^”:µ of the forest^{hZeUMO”¶‘} with^{±ƒ~ q}  r6®·

]  , i.e., removing^” from^e splits^h in a number of disjoint trees, and each connected component has its vertices in the bags of the nodes in only one of these subtrees.

Choose an arbitrary root^š°@{e , and view^h as a rooted tree. We will process^h in a bottom-up order: a node is processed after all its children are processed. While processing vertices, we maintain a set^”

S

~Ae , which is initially empty, and a set^ˆxœ~Oˆ , for which initially^ˆxœ¶'nˆ . The idea is that nodes are added to^”

S

until finally the requested set is found, and that^ˆxœ gives those vertices in^ˆ that still can belong to a connected component with too many vertices in^ˆ in it.

For a node^cY@me , let^{)j_l' q}  rsz¸

]`_, with^e_ the set containing^c and all its descendants in^h . While processing a node^c, compute^{¹H_'†)H_ | ˆxœ}. If^a¹w_<a ºƒ© , put^c in^”

S

, and setˆxœY'¨ˆ»MA¹H_. Otherwise, nothing is done when processing node^c.

We now claim that the set ^”

S

which is obtained after processing root node^š fulfils the requirements of the lemma. Consider a connected component ^± of ^{&`)¼M q}  r6®^¯

]`_‘. Let ^c£µ be the highest node in^h whose bag contains a vertex in ^± . Clearly, ^{c£µ¾½@”}

S

, as ^{±¿~§)¨M q}  r6®¯

]`_. Hence, when^c\µ was processed, ^{a¹H_·ÀaÀ–Á©} . Now we note that ^{± | ˆ ~¨¹H_·} : suppose^{?O@’± | ˆ} . By choice of^c£µ ,

?f@“)j_· . If ?f@ˆÂM’ˆxœ, then ^? belongs to a bag that is below a node in ^”

S

or in ^”

S

, and hence either^? belongs to^q 

r6® ¯

]`_ or is separated from ^± by^q  r6® ¯

]`_. This contradicts that^?@K± , hence

± | ˆ~n± | ˆxœÃ~A¹ _· , and we have^{a± | ˆ¨aT–Ba¹ _·ÀaR–K©} .

To each node^cY@”

S

, we can associate the^©lDÄJ or more vertices that are removed from^ˆxœ when^c was added to^”

S

. As each vertex in^ˆ is associated with at most one^cY@”

S

, we have^a•”

S

aR–†«š¬( ©DnJ^.z­ . 2. First, obtain a set^”

S

as above. As in Lemma 2.1 on the preceding page, create set^”

7

, such that

p

a•”

7

a–#— «š¬(©‚DnJ^.z­MOJ /

p ” S

~’”

S

.

p Every subtree of^{hZeQM” ‘} is adjacent to at most two nodes in^” .

Now, let^± be a connected component of^{&`)BM q}  r6®²

]  ‘. By the properties of tree decompositions, it follows that there is a subtree^hõ of^hZeEMA”

7 ‘, such that all vertices of^± only belong to bags of nodes in^hõ . Thus, the vertices that neighbour a vertex in^± but do not belong to^± must belong to a bag^]1_, with^c‚@‡”

7

one of the at most two nodes in^”

7

that are adjacent to^hõ .^¢

Corollary 2.3 Let&Å'Å()Y*<,Z. have treewidth at most^$ and maximum degree at most^% . Let^ˆÆ~ƒ) ,

aˆ¨aR–Oš . Let^©Uªš . There exists a set^ÇA~#) of at most( $bDAJL.˜>( — «š¬(©NDAJL.z­€MÄJ^. vertices, such every connected component^± in^{&`)xM³Çl‘} contains at most^© vertices from^ˆ and at most^(—$EDO—.G% vertices that are adjacent to a vertex in^Ç . If^$ is a constant, such a set^Ç can be found in linear time.

Proof: The non-algorithmic result follows directly from the previous lemma. (Note that for such a component^ˆ , there are at most^—$°Dn— vertices in ^Ç adjacent to vertices in^ˆ (namely the vertices in at most two bags of the tree decomposition), hence at most (—$ZD#—6.£% vertices in^ˆ that are adjacent to a vertex in^Ç .) To effectively obtain the set^Ç , first apply the algorithm in [Bod96] to obtain an arbitrary tree decomposition of width at most^$ . It is not hard to see that the proofs given above then can be carried out in linear time. ^¢

3 The domino treewidth theorem

In this section, we prove the main result of this section. The technique is inspired by a technique from [BGHK95], which was again inspired by a technique from [RS95].

Theorem 3.1 Let&o'ƒ( )+*-,Z. be a graph with treewidth at most^$ and maximum degree at most^% . Then the domino treewidth of^& is at most( C6$EDAF.£%w(4%QDKJL.lMAJ .

Proof:

We first give a recursive procedure, called MAKEDEC, called with two arguments: a graph ^{È '}

( )HÉ"*<,ÉQ. (which is always an induced subgraph of ^& , and is assumed to have treewidth at most ^$ , and maximum degree at most^% ), and a set of vertices^{ˆ‰~t) É} . The procedure outputs a rooted domino tree decomposition of^È ,^(\[]œ_

ac+@ve6œ4g6*-hbœj'o( e6œ*<kEœÊ.-. of width at most(4C:$IDÄF.£%w(4%bDAJ^.ËM³J , such that the vertices in^ˆ only belong to the bag of the root node of the domino tree decomposition.

ProcedureMAKEDEC(graph^{Ⱦ'ƒ( ) É *-, É .}, vertex set^ˆ ) has the following steps:

1. Obtain a set^ÇA~K)jÉ , such that every connected component of^{ȳ)jÉOMÇl‘} contains at most^=:$™DŒ—

vertices from ^ˆ and at most ( —6$`Dt—6.£% vertices that are adjacent to a vertex in^Ç , (as in Corol- lary 2.3.)

2. Set^{Ìx' Š ( Ç}

›

ˆf. .

3. Compute the connected components^È

S

'o( )

S

*<,

S ., . . . ,È1Í'ƒ( )wÍL*-,bÍ. of^ȳ)HÉKMŒÇMĈ’‘. 4. For each^c,^JE–AcY–K© , callMAKEDEC(^È1_,^{)j_ | Ì} ).

5. Combine the tree decompositions obtained in the previous step in the following way: Take a new

node^š with^]1Îb'tÌ

› Ç › ˆ . This is the root of the new tree decomposition. Make^š adjacent to the roots of each of the tree decompositions, obtained in the previous step. The result is the output of the procedure.

Assume that the set^Ç found in Step 1 is at most of the size, guaranteed to exist by Corollary 2.3 on the preceding page, i.e., we have:

aÇaR–x( $EDnJ^.N˜(—Ë«

š

©‚DnJ

­MOJ^.

Claim 3.1.1 LetÈi'“( )HÉZ*<,ə. be a connected graph, and^ˆ‰~#)HÉ ,^ˆÏ½'tÐ . WhenMAKEDEC(^Èm*ˆ ) is called, the procedure outputs a rooted domino tree decomposition of^È , such that vertices in^ˆ only belong to the root bag of the domino tree decomposition.

Proof: First, observe that the first parameter of a recursive call toMAKEDECalways is a connected graph, and the second parameter of every recursive call toMAKEDECis always a non-empty set: every connected component of^{ȳ) É M³ÇMĈ’‘} must contain vertices adjacent to^Ç

› ˆ . Thus, the recursive calls done toMAKEDECinvolve graphs with fewer vertices, hence the procedure terminates.

Let[Ñl*G?Hg"@‡,bÉ . If ^{[Ñl*G?Hg | ( Ç}

›

ˆf.E½'xÐ , then^Ñ and^? belong both to the root bag^{] Î} . Otherwise,

Ò and^Ó belong to the same connected component^È1_ of^ȳ)HÉOM‡ÇvM‡ˆ’‘, and by induction, there will be a bag containing both^Ò and^Ó . In both cases, there is a bag in the resulting decomposition that contains both^Ò and^Ó .

Let^?d@v)HÉ . There are three cases.

If^?d@Ç

› ˆ , then^? does not belong to any connected component of^{ȳ) É M³ÇMĈ’‘}, hence^? only belongs to bag^]1Î , and no other bag of the decomposition.

If^?K@’Ì , then^? belongs to^{] Î} . In addition, ^? belongs to exactly one connected component^È1_ of

ȳ)HÉBM³ÇŒMˆ’‘. By induction,^? belongs to the root bag of the domino tree decomposition yielded by

the call ofMAKEDEC(^È1_ ,^{)H_ | Ì} ) and no other bag. Thus,^? belongs to exactly two bags that are adjacent.

If^?“½@ƒÌ

› Ç › ˆ , then ^? belongs to exactly one connected component ^{È _} of ^{ȳ) É MtÇOMtˆ’‘}, and by induction to one or two adjacent bags in the decomposition made by the recursive call to

MAKEDEC(^{È _},^{) _H| Ì} ).^? does not belong to any other bag.

Hence, the claim follows.^¢

Claim 3.1.2 IfMAKEDEC(^Èm*<ˆ ) is called with^{ÈX'Ô( ) É *<, É .} a connected graph of maximum degree

% and treewidth at most ^$ , and ^{ˆ ~†)HÉ} a set of vertices of size at most (436$1DO=R.£% , then the resulting domino tree decomposition has width at most(4C:$QDOF!.G%H( %™DnJ^.lMOJ .

Proof: First, we estimate the size of the root bag of the resulting domino tree decomposition. We

have^aˆ¨aR–B(43:$QD³=:.G% . By Corollary 2.3 on the page before, we can take:

aÇaR–x( $UDnJ^.(—Ë«G(436$QD³=:.£%¬(4=:$EDÕ6.z­MOJ^.€ªOÕj($UDKJL.£%

Now

aÌ`a¿– %U˜6aÇ ›

ˆ¨a

– %U˜(-(43:$UDÄ=R.£%IDÕj($QDnJ^.G%:.

' (4C:$QDOF!.G%H( %™DnJ^.

So,

aÌ Ç ˆ¨aR–’( C6$EDOF!.£%w(4%QDKJL.

Secondly, we estimate the size of a set^{)j_ | Ì} in a recursive callMAKEDEC(^È1_,^{)j_ | Ì} ). Write

) _j| Ìx'o() _j|

Š

(ÇY.G.

›

() _w|

Š

( ˆf.G.

Each connected component^{È _} of^{ȳ) É MdÇ1Mdˆ’‘} is contained in a connected component^È _^œ of^{ȳ) É M}

Çl‘. ^Ȝ_ contains at most^=R$ZD#— vertices from^ˆ , hence at most (=:$"DK—.G% vertices of

Š

( ˆf.. Also, by construction of^Ç ,^Ȝ_ contains at most^{(—$EDA—.£%} vertices in

Š

( ÇY.. As a consequence,

a) _j| Ì`aR–x(=:$EDA—.G%IDn(—$EDA—.£%°'o( 36$EDÄ=R.£%

Now, we can use induction: each recursive call ofMAKEDECis called with as second parameter a set of size at most( 36$…D‡=:.G% , hence the recursive calls give tree decompositions of width at most(4C6$…DŒF!.G%H( %€D J^.lMOJ , which proves the claim.^¢

So, from these two claims it follows, that when we callMAKEDEC(^& ,^ˆ ) for a connected graph^& of treewidth at most^$ , and maximum degree at most^% , and any non-empty vertex subset^ˆ which has size at most( 36$EDÄ=R.£% , we obtain a domino tree decomposition of^& of width at most( C6$EDOF!.£%w(4%QDKJL.lMAJ .

If^& is not connected, then make separate domino tree decompositions for each connected component,

and connect these to a tree in an arbitrary way.^¢

The new idea in the proof can be found in step 2 of the procedureMAKEDEC: by adding the neighbours of the vertices in set^Ç

› ˆ to the root bag of the tree decomposition to make, we do not have to use these vertices at lower levels of the tree decomposition anymore. Apart from this idea, the structure of the algorithm is similar to algorithms found in [RS95, BGHK95].

Corollary 3.2 Let^$ be a constant. Given a graph with treewidth at most^$ and maximum degree at most

% , a domino tree decomposition of^& of width at most( C6$EDOF!.£%w(4%QDKJL.lMAJ can be built in^{Ö1(4×Ã7^.} time.

Proof: Use the procedure, given in the proof above. Excluding the time spent in recursive calls of

MAKEDEC, one call ofMAKEDECuses^Ö1(4×Ë. time. There are^Ö1(4×Ë. such calls (e.g., every vertex belongs to at most two bags, hence a tree decomposition with^Ö1(4×Ë. nodes is obtained, and the number of recursive calls ofMAKEDECequals the number of nodes of the resulting tree decomposition), so the total time is bounded by^Ö1(×Ã7L. .^¢

4 A lower bound

In this section, we show that a general bound like obtained in the previous section must always be of order

PQ( $%R..

We first start with the following lemma, which is also interesting on its own. For a graph&“'( )+*-,Z. , let

& 7

'o( )+*[[^?H*-uEgUa>[^?H*-uEgU@m,#ØvŽ

Ò

@v)[^?H*

Ò

gU@v,nه[

Ò

*-uEgU@v,1gL.

Lemma 4.1 Let&f'ƒ( )+*-,". be a graph with domino treewidth at most^$ . The treewidth of^&E7 is at most

—$ .

Proof: W.l.o.g., suppose^& is connected. Let^{(\[^] _} a8c‚@{ejg6*-hK'o(4eH*-kU.G. be a domino tree decompo- sition of^& of width at most^$ . Note that (by the properties of tree decompositions and the assumption of connectedness of^& ) each two adjacent bags intersect. Choose an arbitrary root^š . If we add to each bag

Fig. 1: Grid with added vertices^ÚÛ

] _ the bag of the parent of^c (unless ^c'ƒš ), then we obtain a tree decomposition of ^& of width at most

—$ . (The union of two bags with a non-empty intersection and with size at most^$QDnJ each is taken.) For every edge^[?w*GuUg in^&E7, we have a bag containing both^? and^u : this is trivially true if[^?H*-uEgU@v, . If^? and^u have a common neighbour^Ò in^& , then either there is a bag^{] _} containing both^? , ^u ,^Ò , or there are two adjacent bags, one containing^? and^Ò , and one containing^u and^Ò . One must be a child in

h (with root^š ) of the other. Thus,^? ,^u , and^Ò all three belong to a common bag in the constructed tree decomposition.^¢

AJ>¬>ÕUM#—6¬!Õ -separator of a set W in a graph&Å'¾()Y*<,Z., is a set of vertices^Ç , such that^ˆ can be partitioned into sets^ˆ

S

,^ˆ

7

, and^ˆ

9

, with^ˆ

9

'fÇ | ˆ ,^aˆ

S

aw–B—:¬>Õwaˆ¨a,^aˆ

7

aw–’—:¬>ÕHaˆ¨a, and every path from a vertex in^ˆ

S

to a vertex in^ˆ

7

uses a vertex in^Ç .

The following lemma is well known. See e.g. [BGHK95, GRE84, Liu90, RS86].

Lemma 4.2 Let &Ü'Ý()Y*<,Z. be a graph of treewidth at most ^$ . Let ^{ˆ ~X)} . Then ^& contains a

JL¬>ՙMė6¬!Õ -separator of^ˆ of size at most^$QDnJ .

Lemma 4.3 For all ^%³Þ¼; , ^$Oކ— ,^$ even, there exists a graph^& with treewidth at most^$ , maximum degree at most^% , and domino treewidth at least ^S

S7

$%ZMŒ— . Proof: Consider the following graph.

First, we take a grid of size ^$j¬— by ^{%67^$} . I.e., we have vertices of the form ^?!_ß , J’–àcŒ–¥$j¬— ,

JZ–³yd–n%67L$ , and^?!_ß is adjacent to^{?!_Êá4ß á}, iff^ac MŒc\œzaDBayZMy:œa'ƒJ . To this grid, we add^$H¬!— additional vertices^â

S

*ããã*-â }ä

7

, with, for each^c, Jd–fc™–ƒ$H¬!— ,^{â _} adjacent to each vertex^{? _4ßåæ8}} , ^Jd–ty–o% . Let

&x'ƒ( )+*-,Z. be the resulting graph.

See Figure 1 for an illustration of the construction. (In order to make the figure not too large, the distance between successive neighbours of the vertices^âL_ is 4 in the figure, instead of^%R$ .)

The maximum degree of ^& is ^{/`0>2 ( ;T*-%R.}: vertices of the form^?!_ß have degree at most five, while vertices of the form^âL_ have degree^% . It is also not hard to see that the treewidth of^& is at most^$ . The

$j¬!— by^{%67^$} grid graph has treewidth exactly^$j¬— (see e.g. [Bod98].) As^& contains^$j¬!— vertices such that when these are deleted from^& ,^& becomes a graph of treewidth^$j¬!— , the treewidth of^& is at most^$ . (See e.g. [Bod98], Lemma 72.)

Call the^cth row the set of all vertices of the form^?!_4ß ,^{J°–Oyv–B% 7 $} . Similar, the set of all vertices of the form^?!_4ß ,JE–OcY–K$j¬!— is called the^y th column.

Now, we claim that^&E7 has treewidth at least ^{Sç %R$`MtJ} . Note that all vertices in the^cth row that were

adjacent to^âL_ form a clique in^&E7 . Call the set of these vertices the^cth row-clique. Let

ˆ»'x[^? _ß™a6JE–c‚–#$H¬!—*+JE–y`–K$%

7 g

I.e.,^ˆ is the set of the grid vertices in^& .

Suppose ^Ç is a J>¬>ՋMx—6¬!Õ -separator of ^ˆ of minimum size in ^&E7 , partitioning ^ˆ into ^ˆ

S

, ^ˆ

7

,

ˆ 9

'tÇ | ˆ .

We will now show that^{aÇaRÞ Sç %R$} . Assume ^{aÇa:ª Sç %R$} . Note that^aˆ

S

a–

79

˜^%67^$7^¬— , hence^aˆ

7 | ˆ 9 aRÞ¨S

ç

%:7$7 , and likewise^aˆ

S | ˆ 9 aކS

ç

%67L$7 . Every column that contains both a vertex in^ˆ

S

and a vertex in^ˆ

7

must also contain a vertex in^Ç . Thus, we may assume there are fewer than ^{çS %R$} such columns. So, fewer than ^S

S 7

%R$7 vertices in^ˆ can belong to such a column. It follows that there are at least^{( Sç %67L$7wM S}

S 7

%R$7^.-¬($j¬!—6.À' S9

%67^$YM Sç

%R$ columns that only contain vertices in^ˆ

S

, and thus, every row contains ^S

9

%67^$ÀM Sç

%:$ vertices in^ˆ

S

. Likewise, every row contains ^S

9

%:7^$"MoS

ç

%R$ in^ˆ

7

.

We now will show that every row contains at least ^S

9

%R$ vertices in^Ç .

Consider the^cth row. Note that either all vertices in the^cth row-clique belong to^ˆ

SN›

Ç or all vertices in the^cth row-clique belong to^ˆ

7 › Ç . Without loss of generality, we suppose the former; the other case is identical.

We partition the vertices in the ^cth row in ^% intervals, where the ^è th interval contains vertices

?

_ߟéëêIì

S£í æ8}î

S

*-?

_ߟéÊêbì

S£í æ8}8î

7

*ããã*G?!_4ßê æ8} . At least ^{ï£( S}

9

%:7$vM Sç

%:$j.-¬( %:$j.zð³Þ S

9 % of these intervals must contain vertices in^ˆ

7

. However, each interval also contains a vertex in the^cth row-clique, hence it con- tains a vertex in^Ç

› ˆ S

. So, each interval that contains a vertex in^ˆ

7

must contain a vertex in^Ç , hence the^cth row contains at least ^S

9 % vertices in^Ç .

As we have^$j¬!— rows, it follows that ^{aÇaHÞ¾Sç %:$} . By Lemma 4.2 on the page before, we have that the treewidth of^&E7 is at least ^{Sç %:$‹MnJ} , hence by Lemma 4.1 on page 146, the domino treewidth of^& is at least ^S

S7

%R$°Mė .^¢

5 Final remarks

It is possible to give a modified version of the procedure of Corollary 3.2 on page 146, that yields domino tree decompositions of somewhat larger width (but still ofÖ1( $%:7>., but that usesÖ1(×Qñëò6ó+×Ë. time instead

of^Ö1(×Ã7L. time. However, the proof in [BE97] can be turned into an algorithm that uses linear time. It is

not known how much time a procedure based upon the proof by Ding and Oporowski [DO95] would take.

The proof given in this paper seems unable to yield linear time algorithms - the approach typically leads to algorithmic results ofPQ(×Qñëò6óY×Ë. time. It is open whether domino tree decompositions ofÖ1($%67>. width can be obtained with a linear time algorithm.

Another interesting open problem is whether a bound of^{Ö1($ 7 %:.} can essentially be improved. It would be interesting to see if better bounds, e.g., a bound of^{Ö1( $%R.} can be proved, and whether better lower bounds are possible.

In some special cases, better bounds can be obtained. For instance, for trees we have the following easy result.

Theorem 5.1 The domino treewidth of a tree is at most its maximum degree.

Proof: Let^h be a tree with maximum degree^% . Choose an arbitrary root^š , and view^h as a rooted tree. Lethbœ¶'( )Uœ *-,Zœ´. be the tree, obtained by removing all leaves from^h . Consider the following tree decomposition of^h : (£[]`ôQa?õ@m)Uœ4g6*-hbœë., where each set<sup>]`ô</sup> consists of^? and all children of^? in^h . One easily verifies that this is a domino tree decomposition of^h with width at most^% .^¢

So for trees (and similarly for forests), the domino treewidth is linear in its degree. (Note also that the domino treewidth of a graph with maximum degree^%vޓJ is at least ï£( %QD’JL.-¬!—>ðbM#J : at most two bags can contain a vertex of degree^% and all its neighbours.) It seems interesting to see if it is also possible to obtain similar bounds for other restricted classes of graphs of bounded treewidth, e.g., series parallel graphs, Halin graphs, or arbitrary graphs of treewidth two.

References

[BE97] Hans L. Bodlaender and Joost Engelfriet. Domino treewidth. J. Algorithms, 24:94–123, 1997.

[BGHK95] Hans L. Bodlaender, John R. Gilbert, H. Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, and minimum elimination tree height. J. Algorithms, 18:238–255, 1995.

[Bod96] Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25:1305–1317, 1996.

[Bod98] Hans L. Bodlaender. A partial^$ -arboretum of graphs with bounded treewidth. Theor. Comp.

Sc., 209:1–45, 1998.

[DO95] Guoli Ding and Bogdan Oporowski. Some results on tree decomposition of graphs. J. Graph Theory, 20:481–499, 1995.

[GRE84] John R. Gilbert, Donald J. Rose, and Anders Edenbrandt. A separator theorem for chordal graphs. SIAM J. Alg. Disc. Meth., 5:306–313, 1984.

[Liu90] J. W. H. Liu. The role of elimination trees in sparse factorization. SIAM J. Matrix Analysis and Applications, 11:134–172, 1990.

[RS86] Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width.

J. Algorithms, 7:309–322, 1986.

[RS95] Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. J.

Comb. Theory Series B, 63:65–110, 1995.