Contraction degeneracy on cographs

Contraction Degeneracy on Cographs Hans L.Bodlaender and Thomas Wolle

institute of information and computing sciences,utrecht university technical report UU-CS-2004-031

www.cs.uu.nl

Contraction Degeneracy on Cographs

Hans L.Bodlaender and Thomas Wolle

Institute of Information and Computing Sciences,Utrecht University

P.O.Box80.089,3508TB Utrecht,The Netherlands

hansb@cs.uu.nl thomasw@cs.uu.nl

Abstract.The contraction degeneracy of a graph G is the maximum minimum degree of G

over all minors G of G.The corresponding decision problem is known to be NP-complete.

In this paper,we present a dynamic programming approach for computing the contraction

degeneracy of cographs.

1Introduction

Contracting an edge in a graph is the operation that introduces a new vertex and new edges such that the new vertex is adjacent to all the neighbours of the endpoints of the contracted edge,and then we delete the endpoints of the contracted edge and all their incident edges.Contracting edges has been shown to be of great use for obtaining new lower bound heuristics for treewidth[2].The new parameter contraction degeneracy arose from this research.However,it is an interesting topic in its own right and not only as a treewidth lower bound.The minimum degree of a graph is a lower bound for its treewidth(see[9,1]),as is the maximum minimum degree(also called degeneracy) over all subgraphs[8].Instead of deleting vertices,we can use edge contraction,which leads to contraction degeneracy?rst de?ned in[2].The according decision problem is NP-complete[2]. Thus,it is interesting to look for special graph classes where the contraction degeneracy can be computed in polynomial time.So far,little is known about this.In this paper,we consider the contraction degeneracy problem for the class of cographs.It should be noted that the treewidth of cographs is polynomial time computable[3],and thus our algorithm,while of independent interest, is not necessary to obtain lower bounds for treewidth of given cographs.

Cographs(also called complement reducible graphs)are graphs with a special structure.They are perfect and form a proper subset of the permutation graphs.Cographs can be de?ned recur-sively using two operations(disjoint union and product,see Section2.3)on singletons.Another characterisation is that cographs are exactly those graphs that do not contain a P4as an induced subgraph.The recursive de?nition enables a cograph being represented by an expression,and in turn,being represented by a tree,from which we can derive the cotree of the graph[5].Very often, a dynamic programming approach can be applied to such a cotree,enabling e?cient algorithms on cographs for problems that are NP-hard on general graphs.

The paper is organised as follows.In Section2,we?x some terminology and give more detailed information about edge contractions(Section2.1),the contraction degeneracy(Section2.2)and cographs(Section2.3).Section3presents our dynamic programming method.The lemmas showing the correctness of our approach are given in Section3.1and3.2,followed by the main result in Section3.3.The paper is closed with some remarks in Section4.

2Preliminaries

Throughout the paper G=(V,E)denotes a simple undirected graph.Most of our terminology is standard graph theory/algorithm terminology.The open neighbourhood N G(v)or simply N(v)of a vertex v∈V is the set of vertices adjacent to v in G.As usual,the degree in G of vertex v is d G(v)or simply d(v),and we have d(v)=|N(v)|.N(S)for S?V denotes the open neighbourhood of S,i.e.N(S)= s∈S N(s)\S.We denote the minimum degree of a vertex in G:

d(v)

δ(G):=min

v∈V

Contraction Degeneracy on Cographs3 After deleting vertices of a graph and their incident edges,we get an induced subgraph.A subgraph is obtained,if we additionally allow deletion of edges.If we furthermore allow edge-contractions (see Section2.1),we get a minor.We explicitely exclude the null graph(the empty graph on0 vertices),as a subgraph or minor of a graph.It is known that the treewidth of a minor of G is at most the treewidth of G(see e.g.[1]).A vertex v is universal in G,if v is adjacent to each vertex w∈V,w=v.

2.1Edge Contraction

A more formal approach to edge contractions as well as basic lemmas,which are summarised here, can be found in[10].Contracting edge e={u,v}in the graph G=(V,E),denoted as G/e,is the operation that introduces a new vertex a e and new edges such that a e is adjacent to all the neighbours of u and v and delete vertices u and v and all edges incident to u or v:

G/e:=(V ,E ),where

V ={a e}∪V\{u,v}

E ={{a e,x}|x∈N({u,v})}∪E\{e ∈E|e ∩e=?}

Contracting all edges of a cycle in a graph means that the last contraction is unnecessary.Hence, a contraction-set is a cycle free set E ?E(G)of edges.Let be e,f∈E.Contracting edges is commutative,i.e.(G/e)/f and(G/f)/e are isomorphic graphs.For a contraction-set E = {e1,e2,...,e p},we de?ne G/E :=G/e1/e2/.../e p.A contraction H of G is a graph such that there exists a contraction-set E with:H=G/E .An edge contraction might decrease the degree of a vertex,but it can never decrease it by more than one.

Note that after each single edge contraction the names of the vertices are updated in the graph. Hence,for two adjacent edges e={u,v}and f={v,w},edge f will be di?erent after contracting edge e,namely in G/e we have f={a e,w}.Using the old names of vertices and edges is formally not correct.However,it is unambiguous which new vertex or edge is meant.Furthermore,using the old names might increase understandability and readability.Thus,we can agree on f representing the same edge in G and in G/e.The same applies also to vertices.

2.2Contraction Degeneracy

In this section,we de?ne the parameterδC–the contraction degeneracy.A few basic statements on the contraction degeneracy can be found in[10].Heuristics and experimental evaluations of these for the contraction degeneracy are given in[2].

The degeneracyδD of a graph is the maximum over all its subgraphs of the minimum degree

of the subgraph.

δD(G):=max

G {δ(G )|G is a subgraph of G}

The parameterδD is known to be a lower bound for treewidth[8].Instead of deleting vertices and edges while recording the minimum degree of the occurring subgraphs,contracting edges experimentally proved to be a very good idea for better treewidth lower bounds[2,7].Inspired by this lower bound,the parameterδC and the according decision problem were de?ned.

De?nition1.The contraction degeneracyδC of a graph G is de?ned as follows:

δC(G):=max

G {δ(G )|G is a minor of G}

Note thatδC(G)is de?ned as the maximum over all minors G of G of the minimum degree of G .Using contractions instead of minors in this de?nition does not lead to an equivalent notion, unless the considered graph G is connected.If G is not connected,it might be necessary to delete one or more connected components,to obtain a minor G of G with maximum minimum degree. The corresponding decision problem is formulated as usual:

4Hans L.Bodlaender and Thomas Wolle

Problem:Contraction Degeneracy

Instance:Graph G=(V,E)and integer k≥0.

Question:Is the contraction degeneracy of G at least k?

Contraction Degeneracy is NP-complete,even for bipartite graphs[2].Therefore,it is in-teresting to look at polynomial time computable special cases.Hence,in Section3of this paper, we look at contraction degeneracy for cographs.

2.3Cographs

Cographs can be represented by a tree,enabling dynamic programming approaches on the tree. There are several equivalent de?nitions of cographs.One is that cographs are exactly those graphs that do not contain a P4(a path with four vertices)as an induced subgraph[5].An alternate, equivalent de?nition requires two operations.

De?nition2.Let be given two graphs G1=(V1,E1)and G2=(V2,E2),V1∩V2=?.

–The disjoint union of G1and G2is

G1∪G2=(V1∪V2,E1∪E2).

–The product of G1and G2is

G1×G2=(V1∪V2,E1∪E2∪{{v1,v2}:v1∈V1∧v2∈V2}).

Note that the operations∪and×are commutative and associative.Hence,the result of a sequence of equal operations is well de?ned,and such a sequence can easily be converted into a tree structure using only the binary versions of these operations.

De?nition3.A graph G is a cograph if and only if one of the following holds:

–|V|=1

–G=G1∪G2∪...∪G p for cographs G1,...,G p.

–G=G1×G2×...×G p for cographs G1,...,G p.

A consequence from this de?nition is that a cograph can be represented as an expression using the operations∪and×on singletons.Such an expression can be represented by a tree from which we can derive the cotree of the cograph.

The cotree T G of G is a labelled tree.Leaves of the cotree are in a one-to-one correspondence with the vertices of the graph.Internal nodes of the cotree are labelled with either‘0’or‘1’.To each node of the cotree,we can associate a cograph in the following manner:Each leaf of the cotree represents a graph with a single vertex,hence a cograph.A0-node represents a cograph that is the disjoint union of the cographs corresponding to the children of the0-node,and a1-node represents a cograph that is the product of the cographs corresponding to the children of that1-node.Note that there is an edge between two vertices v and w if and only if the lowest common ancestor of v and w in the cotree is a1-node.There are linear time algorithms for recognising cographs and building the cotree[6,4].

In De?nition3,we can restrict p to be2.As a consequence,a cotree is a binary tree.This is very helpful for formulating dynamic programming algorithms on trees.The size of such a binary cotree T G of cograph G is linear in the size of G,because T G has exactly n=|V(G)|leaves, and after at most O(n)nonempty disjoint union or product operations,we obtain the graph G. Therefore,we have at most O(n)internal nodes in T G.In the following,we assume that the cotree is a binary cotree,i.e.‘cotree’refers to‘binary cotree’.Clearly,the contraction degeneracy of a disconnected graph is the minimum contraction degeneracy of its connected components.Thus, we may assume that the given cograph is connected,and hence,the root of the cotree is a1-node.

Contraction Degeneracy on Cographs 5

3Contraction Degeneracy on Cographs

In this section,we present a dynamic programming method for computing the contraction de-generacy of a cograph G .We assume that we are given G with a binary cotree T (otherwise,a cotree can be build in linear time [6,4],from which a binary cotree can be easily constructed).The special structure of a binary cotree makes it easier to present a dynamic programming algorithm.As already described earlier,cotrees have two kind of internal nodes:1-nodes and 0-nodes.Every node i represents a subgraph G i of the input graph G .Each internal node i of a binary cotree has exactly two children j 1and j 2.When considering a 0-node i of a cotree,the graph G i is simply the disjoint union of the two graphs G j 1and G j 2.Consequently,all edges that can be contracted in G i can either be contracted in G j 1or in G j 2.However,if i is an 1-node,new edges are created between vertices of G j 1and vertices of G j 2.Hence,not all edges that can be contracted in G i can be contracted in G j 1or in G j 2.Consider some ?xed internal node i of T with children j 1and j 2.We use the following terminology:

–G i is the graph corresponding to node i ,i.e.G i =G j 1∪G j 2if i is a 0-node,and G i =G j 1×G j 2if i is a 1-node.

–V i =V (G i ),V j 1=V (G j 1),V j 2=V (G j 2).–E i =E (G i ),E j 1=E (G j 1),E j 2=E (G j 2).–n i =|V i |.–e ∈E i is called a cross edge if i is a 1-node and e ∈E j 1∪E j 2.–G \V =G [V \V ]for a graph G =(V,E )and V ?V .

The following lemma is easy to see,but it is an important part of the correctness proof of our approach.

Lemma 1.Contracting a cross edge of G i creates a universal vertex in G i .

Proof.Given a cross edge e ={u,v },u ∈V j 1and v ∈V j 2,we know by de?nition of a 1-node,that u is adjacent to all w ∈V j 2in G i .Also,v is adjacent to all w ∈V j 1in G i .When contracting e ,we get a vertex,adjacent to all w ∈V i \e in G i .

In our dynamic programming approach,we associate to each node i ,i.e.to each subgraph G i ,a function

F i :I N ×I N ?→I N

For nonnegative integers x and y with x +y ≤n i ,x ≤n i ?1,the function F i is de?ned in the following way:

F i (x,y )=max {δ(H )|H can be obtained from

G i by

contracting the edges of a contraction-set of size x

and then deleting y vertices and their incident edges }

A table T i with O (n 2i )entries can be used to store the values of F i .The table contains a tuple for every possible x -y -combination.Each tuple consists of three integers (x,y,z ),with z =F i (x,y ).

The motivation behind storing the maximum minimum degree after x edge contractions and y vertex deletions is as follows.When considering a graph G i ,we can contract edges in E (G i )to increase the minimum degree.We also must consider the possibility that in order to obtain the maximum minimum degree of G ,i.e.to solve the contraction degeneracy problem on G ,it might be necessary to contract some edges not in E (G i )but in E (G h )where h is a 1-node in the cotree that is on the path from i to the root r of the cotree.Deleting a vertex can decrease the minimum degree.However,we do not delete vertices from the graph G i ,we only ‘deactivate’them,such that they have no in?uence on the degrees at this moment.In a later stage,deactivated vertices might be used for contracting cross edges,which results in universal vertices (see Lemma 1).The consequences of the introduction of a universal vertex are easily computable,since the degree of each vertex is increased by one.That is the reason why we ?rst ‘deactivate’some vertices and later using them again (not explicitely).In the next lemma,we see that we indeed can compute the contraction degeneracy of a cograph by using function F i .

6Hans L.Bodlaender and Thomas Wolle

Lemma 2.Given the function F i de?ned above for node i of a binary cotree,we can solve the contraction degeneracy problem for G i in O (n i )time.

Proof.To solve the problem on G i means that we can only use contractions of edges in G i to in-crease the minimum degree,and we must not delete any vertices.For every number x of contracted edges in G i ,and every number y of deleted vertices,we have the maximum minimum degree.For the contraction degeneracy problem,we only need these values with y =0.Clearly,we have:

δC (G i )=max x =0,...,n i ?1F i (x,0)

Hence,if we have the function F r for the root r of the cotree,i.e.G r =G ,we can compute the contraction degeneracy of G in O (n )additional time.Now we have seen that the functions F i are su?cient to solve the problem,we look at how to compute these for each node i ,using the functions for the children of i .As giving such a function for a leaf node i is trivial (there are just two values F i (0,0)=0and F i (0,1)=∞),we describe the methods to compute the values of these functions for 0-nodes and for 1-nodes.

3.1A Recurrence Relation for 0-nodes

In this section,we give the recurrence relation for a 0-node i with children j 1and j 2,i.e.we present and prove the correctness of the recursive formula to compute F i using the already computed values of functions F j 1and F j 2.

Lemma 3.Let i be a 0-node with children j 1and j 2,x and y nonnegative integers with x +y ≤n i ,x ≤n i ?1.Then,we have:

F i (x,y )=max {min(F j 1(x 1,y 1),F j 2(x 2,y 2))|

x 1,x 2,y 1,y 2∈I N ∧x 1+x 2=x ∧y 1+y 2=y ∧

x 1≤n j 1?1∧x 2≤n j 2?1}

Proof.Let x and y be ?xed nonnegative integers with x +y ≤n i ,x ≤n i ?1.First,we will prove that F i (x,y )is at least the stated expression.

Claim.Let x 1,y 1,x 2,and y 2be ?xed integers with x 1+x 2=x ,y 1+y 2=y ,x 1≤n j 1?1and x 2≤n j 2?1.Then F i (x,y )≥min(F j 1(x 1,y 1),F j 2(x 2,y 2)).

Proof.Let E 1be the contraction-set with |E 1|=x 1,and let V 1be the vertex set with |V 1|=y 1,such that:F j 1(x 1,y 1)=δ((G j 1/E 1)\V 1).E 2and V 2are de?ned similarly.

Now we can contract in G i the contraction-set E 1∪E 2,and then delete all vertices in V 1∪V 2.Since F i (x,y )is de?ned to be a maximum value,and (G i /(E 1∪E 2)\(V 1∪V 2)is a pos-sible minor (see the de?nition of F i ),we have:F i (x,y )≥δ((G i /(E 1∪E 2))\(V 1∪V 2))=min(F j 1(x 1,y 1),F j 2(x 2,y 2)). As the claim holds for all nonnegative integers x 1,y 1,x 2,and y 2with x 1+x 2=x ,y 1+y 2=y ,x 1≤n j 1?1and x 2≤n j 2?1,we have:

F i (x,y )≥max {min(F j 1(x 1,y 1),F j 2(x 2,y 2))|

x 1,x 2,y 1,y 2∈I N ∧x 1+x 2=x ∧y 1+y 2=y

x 1≤n j 1?1∧x 2≤n j 2?1}

Now we show that F i (x,y )is at most the stated expression.Consider a contraction-set E ?E with |E |=x ,and a vertex set V ?V with |V |=y ,such that

F i (x,y )=δ((

G i /E )\V )

Note that i is a 0-node,and hence,each edge in E i belongs to E j 1or E j 2.E and V can be partitioned in the following way:

Contraction Degeneracy on Cographs7

E1:=E j

1∩E E2:=E j2∩E V1:=V j1∩V V2:=V j2∩V

x1:=|E1|x2:=|E2|y1:=|V1|y2:=|V2|

Claim.It holds:x1+x2=x,y1+y2=y,x1≤n j1?1and x2≤n j2?1.

Proof.From the partition of E and V directly follows x1+x2=x and y1+y2=y.Each contraction-set is a forest,and hence,each contraction-set has at most n?1edges,where n is the number of vertices in the considered graph.E1is a contraction-set,since E1?E .Therefore,E1 is a contraction-set for G j

1

.Thus,x1≤n j1?1and x2≤n j2?1.

We have G i=G j

1∪G j2and by de?nition of E1,E2,V1and V2,the following is easy to see.

(G i/E )\V =(G j1/E1)\V1∪(G j2/E2)\V2,and therefore,we have:

F i(x,y)=δ((

G i/E )\V )=min(δ((G j1/E1)\V1),δ((G j2/E2)\V2))

So,F i(x,y)≤δ((G j

1/E1)\V1)≤F j

1

(x1,y1).Similarly,F i(x,y)≤F j

2

(x2,y2),and hence,

F i(x,y)≤min(F j

1(x1,y1),F j

2

(x2,y2)).

3.2A Recurrence Relation for1-Nodes

This section is devoted to the recurrence relation for a1-node i with children j1and j2.However, before we present and prove the correctness of the recursive formula to compute F i(using the

already computed values of functions F j

1and F j

2

),we introduce a modi?ed version F i of F i.

The function F i is de?ned especially for1-nodes.The advantage is that it is easier and faster to https://www.docsj.com/doc/d17608411.html,ter,we will show that we can compute F i using function F i.Let i be a1-node with associated graph G i=(V i,E i),and let E c?E i be the set of cross edges of G i.

F i:I N×I N?→I N

For nonnegative integers x and y with x+y≤n i and x≤n i?1,the function F i is de?ned in the following way:

F i(x,y)=max{δ(H)|H can be obtained from

G i by

contracting the edges of a contraction-set E of size x

and then deleting y vertices and their incident edges,

where?e,f∈E c∩E :e∩f=?}

The last requirement in the de?nition of F i says that all cross edges in E are pairwise non-adjacent.Hence,every cross edge in E creates a unique universal vertex.We?rst give a number of lemmas which will be used later.For Lemmas4,5,and6,suppose the following is given.The graph G i=G j

1×G j2is the product of G j1and G j2.Furthermore,let be given contraction-sets E ?E i,|E |=x,E1?E j1and E2?E j2,vertex sets V ?V i,|V |=y,V1?V j1,V2?V j2,with

E1=E ∩E j1,|E1|=x1,E2=E ∩E j2,|E2|=x2,E?=E \(E1∪E2),|E?|=x?,and E?does not contain any two adjacent edges,i.e.?e,f∈E?:e∩f=?.Furthermore,let be V?= e∈E?e, V1=(V j

1∩V )∪V?,|V1|=y1,V2=(V j2∩V )∪V?,|V2|=y2,and y1≥x?,y2≥x?.Note that E?is the set of cross edges that is contracted,and V?is the set of endpoints of edges in E?.

Lemma4.Each of the following holds:

1.|V(G i/E \V )|=n i?x?y.

2.x+y=n i=?F i(x,y)=∞.

3.x+y

Proof.(1.)Note that G i has n i vertices.Since E is a contraction-set,every contraction of an edge in E results in a decrease of the number of vertices by one.Hence,|V(G i/E )|=n i?x.Now,we have to delete y vertices in G i/E .Clearly,|V(G i/E \V )|=n i?x?y.

8Hans L.Bodlaender and Thomas Wolle

(2.)From (1.),we can conclude that G i /E \V is the null graph (the empty graph with 0vertices).Hence,the minimum degree of a vertex over an empty vertex set is the minimum of an empty set of integers,i.e.it is ∞.

(3.)Since G i /E \V has n i ?x ?y vertices,the maximum degree of a vertex in G i /E \V is at most n i ?x ?y ?1.As this holds for every E and V with |E |=x ,|V |=y ,we have F i (x,y )≤n i ?x ?y ?1.

Note that we explicitely excluded the null graph as a minor and as a subgraph of a graph.However,we will use the minimum degree of the null graph in our recurrence relations,i.e.we need statement (2.)of Lemma 4.

Lemma 5.Let v 1∈V (G j 1/E 1\V 1).Then we have:

d G i /E \V (v 1)=d G j 1/E 1\V 1(v 1)+n j 2?x 2?y 2+x ?

Proof.Since E 1and V 1only change the internal structure and number of vertices in G j 1,we have:d (G j 1×G j 2)/E 1\V 1(v 1)=d G j 1/E 1\V 1(v 1)+n j 2.With the same argument that E 2and V 2only a?ect G j 2,we have:d (G j 1×G j 2)/(E 1∪E 2)\(V 1∪V 2)(v 1)=d G j 1/E 1\V 1(v 1)+n j 2?x 2?y 2(see (1.)in Lemma 4).However,instead of deleting all vertices in V 1∪V 2,we contract x ?non-adjacent edges with one endpoint in V 1and the other endpoint in V 2,i.e.we contract all cross edges in E ?.It is easy to see that this results in x ?additional universal vertices (see Lemma 1).Hence,we have:

d (G j 1×G j 2)/(E 1∪E 2∪E ?)\[(V 1∪V 2)\V ?](v 1)=d G j 1/E 1\V 1(v 1)+n j 2?x 2?y 2+x ?

Lemma 6.Let v 1,v 2∈V (G j 1/E 1\V 1).Then we have:

d G j 1/E 1\V 1(v 1)≤d G j 1/E 1\V 1(v 2)??d G i /E \V (v 1)≤d G i /E \V (v 2)

Proof.This follows directly from Lemma 5.

Lemma 7.If x +y =n i ,then F i (x,y )=∞.

Proof.This is similar to Lemma 4(2).

Now in Lemmas 8and 9,we give the recurrence relation for 1-nodes.

Lemma 8.Let i be a 1-node with children j 1and j 2.Let x and y be nonnegative integers with x +y ≤n i ,x ≤n i ?1.Then,we have:

F i (x,y )=max {min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)|x 1,x 2,y 1,y 2,x ?∈I N ∧x 1+x 2+x ?=x ∧y 1+y 2=y +2·x ?∧y 1≥x ?∧y 2≥x ?∧x 1+y 1≤n j 1∧x 2+y 2≤n j 2

x 1≤n j 1∧x 2≤n j 2}

Proof.Let x and y be ?xed nonnegative integers with x +y ≤n i ,x ≤n i ?1.We will ?rst prove that F i (x,y )is at least the stated expression.Therefore,let x 1,x 2,y 1,y 2,and x ?be ?xed nonnegative integers ful?lling the requirements stated in the lemma.We will ?rst prove:

F i (x,y )≥min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)

Contraction Degeneracy on Cographs 9

Let E 1and E 2be contraction-sets with |E 1|=x 1and |E 2|=x 2and V 1and V 2be set of vertices with |V 1|=y 1and |V 2|=y 2,such that F j 1(x 1,y 1)=δ(G j 1/E 1\V 1)and F j 2(x 2,y 2)=δ(G j 2/E 2\V 2).Let E ?be a set of x ?pairwise non-adjacent cross edges,each of them having one endpoint in V 1and the other in V 2,and let be V ?= e ∈E ?e .As |V 1|=y 1≥x ?and |V 2|=y 2≥x ?,and each vertex in V 1is adjacent to each vertex in V 2,we can choose such a set E ?.We de?ne:E :=E 1∪E 2∪E ?and V :=(V 1∪V 2)\V ?.

Claim.|E |=x and |V |=y .

Proof.This follows from the de?nition of the corresponding sets.Note that E 1,E 2and E ?are pairwise disjoint.Furthermore,observe that V 1and V 2are disjoint and V ??(V 1∪V 2).Hence,|V |=|V 1|+|V 2|?|V ?|=y 1+y 2?2·x ?.

Note that V (G i /E \V )can be partitioned into three disjoint sets:W 1:=V (G j 1/E 1\V 1),W 2:=V (G j 2/E 2\V 2),and the vertices that result from contracting a cross edge W ?:=V (G i /E \V )\(W 1∪W 2).

If W 1is empty,then x 1+y 1=n j 1and F j 1(x 1,y 1)=∞.Otherwise,let v 1be a vertex in G j 1/E 1\V 1of minimum degree,i.e.d G j 1/E 1\V 1(v 1)=F j 1(x 1,y 1).From Lemma 6,we know that all other vertices in G j 1/E 1\V 1have degree in G i /E \V as least as large as the degree of v 1in G i /E \V .So,by Lemma 5all vertices in W 1have degree at least d G j 1/E 1\V 1(v 1)+n j 2?x 2?y 2+x ?≥F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?.Similarly,either W 2is empty,in which case F j 2(x 2,y 2)=∞,or all vertices in W 2have degree at least F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?.

Vertices that are the result of a contraction of a cross edge are universal in G i /E \V ,and hence have degree n i ?x ?y ?1.We can conclude that

F i (x,y )≥δ(

G i /E \V )

≥min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)

Since this holds for all x 1,x 2,y 1,y 2and x ?,ful?lling the conditions as in the lemma,we can conclude:

F i (x,y )≥max {min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)|x 1,x 2,y 1,y 2,x ?∈I N ∧x 1+x 2+x ?=x ∧y 1+y 2=y +2·x ?∧y 1≥x ?∧y 2≥x ?∧x 1+y 1≤n j 1∧x 2+y 2≤n j 2∧

x 1≤n j 1∧x 2≤n j 2}

We now show the equality,i.e.we show that F i (x,y )is at most the given expression.Let E be a contraction-set of size x containing no two adjacent cross edges,and V be a vertex set of size y such that F i (x,y )=δ(G i /E \V ).E and V can be partitioned in the following way:

E 1:=E j 1∩E E 2:=E j 2∩E E ?:=E \(E 1∪E 2)V 1:=V j 1∩(V ∪V ?)V 2:=V j 2∩(V ∪V ?)V ?:= e ∈E ?e x 1:=|E 1|x 2:=|E 2|x ?:=|E ?|

y 1:=|V 1|y 2:=|V 2|Claim.x =x 1+x 2+x ?,y 1+y 2=y +2·x ?,y 1≥x ?,y 2≥x ?,x 1+y 1≤n j 1,x 2+y 2≤n j 2,x 1≤n j 1,x 2≤n j 2.

10Hans L.Bodlaender and Thomas Wolle

Proof.The ?rst equality follows directly from the corresponding de?nitions.

Note that E ?is a contraction-set containing all cross edges of E (they are pairwise non-adjacent).Hence,|V ?|=2·x ?.Furthermore,observe that V j 1and V j 2are disjoint and V j 1∪V j 2=V i ?(V ∪V ?).Therefore,y 1+y 2=|V 1|+|V 2|=|V j 1∩(V ∪V ?)∪V j 2∩(V ∪V ?)|=|V i ∩(V ∪V ?)|=|V ∪V ?|=y +2·x ?.

The inequality y 1≥x ?follows from y 1=|V 1|=|V j 1∩(V ∪V ?)|≥|V j 1∩V ?|=|E ?|=x ?.|V j 1∩V ?|=|E ?|can be seen from the fact that E ?contains exactly x ?non-adjacent cross edges that have one endpoint in V j 1and the other endpoint in V j 2.

Since E 1is the subset of E ,restricted to G j 1,E 1is a contraction-set of G j 1,and V 1is a subset of vertices in G j 1/E 1,since V is a subset of vertices in G i /E .Hence,x 1+y 1≤n j 1and x 1≤n j 1.

In the same way,we can conclude y 2≥x ?,x 2+y 2≤n j 2and x 2≤n j 2.

Similar as above,write W 1=V (G j 1/E 1\V 1),W 2=V (G j 2/E 2\V 2)and W ?=V (G i /E \V )\(W 1∪W 2)the set of vertices resulting from contracting a cross edge.Note that W 1,W 2and W ?partition V (G i /E \V ).We consider four di?erent cases.

Case 1‘W 1=?and W 2=?’:In this case,G i /E \V is a clique with x ?vertices,as each vertex in this graph is the result of a contraction of a cross edge.So,δ(G i /E \V )=x ??1=n i ?x ?y ?1.As W 1=?,we must have that n j 1?x ?y ?1,and hence F j 1(x 1,y 1)=∞.Similarly,F j 2(x 2,y 2)=∞.So,

F i (x,y )=δ(

G i /E \V )

=min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)

Case 2‘W 1=?and W 2=?’:First note that W 2=?implies that F j 2(x 2,y 2)=∞,similar to the previous case.Take a vertex v 1∈W 1which has minimum degree in G i /E \V .Note that vertices in W ?are universal in G i /E \V ,hence have degree that is at least the degree of v 1in this graph.So,we have (use Lemmas 5and 6)

F i (x,y )=δ(

G i /E \V )

=d G i /E \V (v 1)

=d G j 1/E 1\V 1(v 1)+n j 2?x 2?y 2+x ?

≤F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?

=min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)

The last step follows by using that F j 2(x 2,y 2)=∞,and noting that F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?≤n j 1?x 1?y 1?1+n j 2?x 2?y 2+x ?=n i ?x ?y ?1.

Case 3‘W 1=?and W 2=?’:Similar to the previous Case 2,with the roles of W 1and W 2exchanged.

Case 4‘W 1=?and W 2=?’:As in Case 2,F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?≤n i ?x ?y ?1,and similar F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?≤n i ?x ?y ?1.Take a vertex v 1∈W 1that has minimum degree in G i /E \V among all vertices in W 1,and similar take a vertex v 2∈W 2with minimum degree in G i /E \V .

Again,vertices in W ?have a degree that is at least the degree of v 1(or v 2)in G i /E \V .So,we have using Lemmas 5and 6

F i (x,y )=δ(

G i /E \V )

Contraction Degeneracy on Cographs 11

=min(d G i /E \V (v 1),d G i /E \V (v 2))

=min(d G j 1/E 1\V 1(v 1)+n j 2?x 2?y 2+x ?,

d G j 2/E 2\V 2(v 2)+n j 1?x 1?y 1+x ?)

≤min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?)=min(F j 1(x 1,y 1)+n j 2?x 2?y 2+x ?,

F j 2(x 2,y 2)+n j 1?x 1?y 1+x ?,

n i ?x ?y ?1)

This ends the last case of the proof,and hence we can conclude Lemma 8. Now we have seen that our recurrence relation for F i is correct,we will show how we can compute F i given F i .

Lemma 9.

F i (x,y )=max 0≤z ≤x

F i (x ?z,y +z )Proof.We will ?rst prove that F i (x,y )≥max 0≤z ≤x F i (x ?z,y +z ).

Claim.F i (x,y )≥F i (x ?1,y +1).

Proof.Let E be a contraction-set of size x ?1without any adjacent cross edges,and let V be a vertex set of size y +1such that:F i (x ?1,y +1)=δ(G i /E \V ).Let v ∈V be a vertex that we deleted in G i /E \V ,i.e.v ∈V .Instead of deleting it,we can contract it using a cross edge e adjacent to v .Since v is not contained in G i /E \V ,contracting it via a cross edge (no matter whether e is adjacent to another cross edge in E ),will not decrease any vertex degree.Note that unless v is the only vertex left,a cross edge incident to v always exists,since G j 1and G j 2are graphs with at least one vertex each.Hence,we have a contraction-set E ∪{e }of x edges and a vertex set V \{v }of y vertices,such that:

F i (x,y )≥δ(

G i /(E ∪{e })\(V \{v }))≥F i (x ?1,y +1)

A similar argument can be used when 2≤z ≤x .Now we contract z vertices with cross edges incident to them instead of deleting them.Thus,for all z ,0≤z ≤x ,we have F i (x,y )≥F i (x ?z,y +z ),and hence

F i (x,y )≥max 0≤z ≤x

F i (x ?z,y +z )(1)We will now show F i (x,y )≤max 0≤z ≤x F i (x ?z,y +z ).Let E be a contraction-set of size x and let be V be a vertex set of size y ,such that F i (x,y )=δ(

G i /E \V ).Let E ??E be the set of all cross edges in E ,and let be V ?:= e ∈E ?e .Observe that (V ?,E ?)is a forest without isolated vertices.Let c be the number of connected components in (V ?,E ?).We modify E ?in the following way to obtain E ??.In each connected component of (V ?,E ?),we delete all but one edge,resulting in the forest (V ?,E ??).Let be V ??:= e ∈E ??e .Clearly,E ??does not contain any two adjacent cross edges and |E ??|=c ,|V ??|=2c .We de?ne:

E :=(E \E ?)∪E ??and V :=V ∪(V ?\V ??)and z :=|E |?|E |

Claim.|E |=|E |?z =x ?z and |V |=|V |+z =y +z .

12Hans L.Bodlaender and Thomas Wolle

Proof.|E |=|E |?z follows directly from the de?nition of z.To see the other equality,note that the vertex sets are disjoint or contained in each other when applying basic operations.Furthermore, note that in a forest,the number of edges plus the number of connected components equals the number of vertices.We therefore have:

|V |=|V ∪(V?\V??)|=|V |+|V?|?|V??|=y+|E?|+c?2c

=y+|E?|?c=y+|E?|?|E??|=y+|E |?|E |+|E?|?|E??|

=y+|E |?(|E |?|E?|+|E??|)=y+|E |?(|E \E?|+|E??|)

=y+|E |?|(E \E?)∪E??|=y+|E |?|E |=y+z

Claim.Let E contain two adjacent cross edges.e={u1,u2}and f={u2,w},such that there is no other edge in E than e adjacent to f.Let v be a vertex in G i/(E \{f})\V .Then it holds: d G

(v)=d G i/(E \{f})\(V ∪{w})(v).

i/E \V

Proof.If w is not adjacent to v then the claim follows easily.So suppose{v,w}is an edge in G i/(E \{f})\V .Since e was(w.l.o.g.)contracted before f,the vertex created by contracting e is a universal vertex a e.Now,we can either delete vertex w,resulting in decreasing the degree of v by one,or we can contract edge f to the universal vertex a e,which also results in‘losing’one edge incident to v,since{a e,v}is already present in G i/(E \{f})\V .Hence,the degree of v is the same in both cases.

Applying the last claim iteratively,we can conclude the following:δ(G i/E \V )=δ(G i/E \ V ).Hence,there is a z,such that F i(x,y)=F i(x?z,y+z).From this fact and Equation1,the lemma follows.

3.3A Dynamic Programming Algorithm for Contraction Degeneracy on Cographs

Now,we are able to formulate our main result.So far,we only presented the recurrence rela-tions necessary for dynamic programming.It is an easy task to transform these relations into an algorithm.

Theorem1.There is an O(n6)time algorithm to compute the contraction degeneracy of a given cograph G with n vertices.

Proof.We?rst build the cotree in linear time[6,4],from which the binary cotree can be easily derived.We then compute in bottom up order for each node i in the cotree the relevant values of F i.For1-nodes,we?rst compute F i.These computations are as dictated by Lemmas3,7,8and9. After the root values are computed,we use Lemma2to compute the contraction degeneracy of G.

For the running time,consider the formula for computing F i on1-nodes,since the computation time of this formula dominates the others.We can implement this formula by?ve nested loops,for x1,x2,y1,y2and x?,running over the appropriate domains(at most{0,...,n i}).In the innermost loop body,we check the restrictions,compute x,y,and the minimum as given in the formula,and we update F i(x,y)if we have found a larger value.This loop takes O(n5)time,and since we have O(n)internal nodes in the cotree,the theorem follows.

It is also possible to obtain in O(n6)time the set of contractions that achieve the contraction degeneracy,using standard techniques for transforming a dynamic programming decision algorithm to one that also constructs solutions.

Contraction Degeneracy on Cographs13 4Discussion

The contraction degeneracy of a graph appears to be an interesting graph parameter.So far,little is known on it.Its strong relation to the well understood minimum degreeδand degeneracyδD of a graph,and its elementary nature make it a worthwhile object of study.In this paper we have presented a dynamic programming method for computing the contraction degeneracy of a cograph. The running time of our algorithm seems surprisingly high,since cographs are a very restricted class of graphs with a tree representation,and they usually enable faster algorithms.This might be a consequence of the possible inherent hardness of computingδC of a graph.However,it remains an interesting topic for further research to decrease the running time for cographs,or to develop algorithms for other special graph classes.

References

1.H.L.Bodlaender.A partial k-arboretum of graphs with bounded https://www.docsj.com/doc/d17608411.html,p.Sc.,

209:1–45,1998.

2.H.L.Bodlaender,A.M.C.A.Koster,and T.Wolle.Contraction and treewidth lower bounds.In

Proceedings12th Annual European Symposium on Algorithms ESA’04,2004.(to appear).

3.H.L.Bodlaender and R.H.M¨o hring.The pathwidth and treewidth of cographs.SIAM J.Disc.

Math.,6:181–188,1993.

4. A.Bretscher,D.Corneil,M.Habib,and C.Paul.A simple linear time LexBFS cograph recognition

algorithm.In H.L.Bodlaender,editor,Proceedings27nd International Workshop on Graph-Theoretic Concepts in Computer Science WG’03,pages119–130,2003.

5. D.G.Corneil,H.Lerchs,and L.Stewart https://www.docsj.com/doc/d17608411.html,plement reducible graphs.Annals Discrete

Math.,1:145–162,1981.

6. D.G.Corneil,Y.Perl,and L.K.Stewart.A linear recognition algorithm for cographs.SIAM J.

Comput.,14:926–934,1985.

7.V.Gogate and R.Dechter.A complete anytime algorithm for treewidth.In Proceedings of the20th

Conference on Uncertainty in Arti?cial Intelligence,2004.(to appear).

8. A.M.C.A.Koster,H.L.Bodlaender,and S.P.M.van Hoesel.Treewidth:Computational exper-

iments.In H.Broersma,U.Faigle,J.Hurink,and S.Pickl,editors,Electronic Notes in Discrete Mathematics,volume8.Elsevier Science Publishers,2001.

9.P.Sche?er.Die Baumweite von Graphen als ein Ma?f¨u r die Kompliziertheit algorithmischer Prob-

leme.PhD thesis,Akademie der Wissenschaften der DDR,Berlin,1989.

10.T.Wolle and H.L.Bodlaender.A note on edge contraction.Technical Report UU-CS-2004-028,

Institute of Information and Computing Sciences,Utrecht University,Utrecht,the Netherland,2004.