Characterizations and linear-time recognition of
probe cographs
Van Bang Le and H.N.de Ridder
Institut f¨u r Informatik,Universit¨a t Rostock,18051Rostock,Germany,
超兽武装2{le,hnridder}@informatik.uni-rostock.de
Cographs are those graphs without induced path on four vertices.A graph G
is a probe cograph if its vertex set can be partitioned into two sets,N(non-probes)
and P(probes)where N is independent and G can be extended to a cograph by adding edges between certain non-probes.A partitioned probe cograph is a
probe cograph with a given partition in N and P.
For convenience,we will use the following notion.For a graph class C and
a graph G=(V,E),a partition V=P∪N with an independent set N is called a valid partition(with respect to C)if there exists E′⊆ N2 such that G′=(V,E∪E′)is a member of C.Such a graph G′is then called a valid exten-
sion for G.Thus,G is a probe graph of C if and only if G has a valid partition, and G=(P,N,E)is a partitioned probe graph of C if and only if V(G)=P∪N is a valid partition.
Probe cographs versus singular cograph contractions Recall that co-graphs(or complement-reducible graphs)[4]are those graphs that can be con-structed from a single vertex by repeated applications of complement and disjoint union.They are precisely the P4-free graphs and are known under many different names and definition;see for example[6].
Cographs were generalized to cograph contractions as follows.A graph G
is called a cograph contraction if there exists a cograph H together with some pairwise disjoint independent sets S1,...,S t in H such that G is obtained from H by contracting each S i to a single vertex s i and then making the vertices s1,...,s t to a clique.Cograph contractions have been introduced and investigated in[5] in connection to graph precoloring extensions and perfection,and have been characterised in[7].
A special case of cograph contractions where all independent sets S1,...,S t
are one-element sets has a close relationship to probe cographs.We formulate this situation in a more general setting.
Definition1.Let C be a class of graphs.A graph G is called a singular C contraction if there exists a graph H∈C together with a(not necessarily inde-pendent)set S of vertices of H such that G is obtained from H by making S to a clique.
Let co-C be the class consisting of the complements of all graphs in C.C is self-complementary if C and co-C coincide.Singular C contractions are related to probe graphs of C as follows.
Dagstuhl Seminar Proceedings 07211
Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes
drops.dagstuhl.de/opus/volltexte/2007/1270
Proposition1.A graph G is a probe graph of C if and only if
魏坤琳 郭敬明
P5has its triangle in Q,and every bull has a vertex of degree one or a vertex of degree two in Q. Characterizing probe cographs Unpartitioned probe cographs can be char-acterized in several ways as follows.
First,for a given graph G=(V,E),a particular2-Sat instance F(G)is created as follows.
sunny王阳明–The boolean variables are the vertices of G,
–for each edge ab of G,(b)is a clause,the edge-clause for ab,
–for each P4=abcd of G,(a∨b)and(c∨d)are two clauses,the P4-clauses for that P4,
–for each P5=abcde of G,(d)are two clauses,the P5-clauses for that P5,
–for each bull of G with the triangle abc where b is the degree-2vertex of the bull,(a∨b)and(c∨b)are two clauses,the bull-clauses for that bull.
The formula F(G)is the conjunction of all edge-clauses,all P4-clauses,all P5-clauses,and all bull-clauses.We will see that G is a probe cograph if and only if F(G)is satisfiable.
Let N be an independent set in G=(V,E).Following[2]we call two vertices x,y in G twins with respect to N if both x,y are in N or outside N and x,y are twins in G,or x∈V\N,y∈N and N(y)−x=N(x)\N.
In a bull,vertices belonging to the triangle of the bull are called mid-points of the bull.何润东和李沁
Theorem2.The following statements are equivalent for any graph G.
(i)G is a probe cograph;
(ii)F(G)is satisfiable;
2
(iii)G admits an independent set N meeting every P4in two vertices,every P5 in three vertices,and every bull in a mid-point;
(iv)
G is obtained from a cograph on the same vertex set by making N to a clique; (vi)Each induced subgraph H of G with at least two vertices has two twins with respect to N∩V(H).
Recognizing probe cographs In[3],Chang et al.give an O(n3)recognition for partitioned probe cographs and an O(n5)recognition for probe cographs (n is the number of vertices of the input graph).Chandler et al.[2]improved this to O(n2)by showing that the recognition of unpartitioned probe cographs can be reduced to the partitioned case in linear time and reducing recognition of partitioned probe cographs to the recognition of partitioned probe distance hereditary graphs,for which they give an O(n2)algorithm.
Using Theorem3(iv)and by modifying the recognition algorithm for cographs due to Corneil at al.[4],we give a linear time recognition algorithm for parti-tioned probe cographs.
As the unpartitioned case can be reduced to the partitioned case in linear time([1,2]),probe cographs therefore can be recognized in linear time.
3
Theorem4.Partitioned and unpartitioned probe cographs can be recognized in linear time.Moreover,a valid extension of a given probe graph can be determined in linear time,too.
Moreover,in the partitioned case,our recognition algorithm produces a cer-tificate for membership tha
t can be checked in linear time(the co-tree of a valid extension)and a certificate for non-membership that can be checked in sublinear time(one of the forbidden subgraphs in Fig.1).
References
1.Daniel Bayer,¨Uber probe-trivially-perfect und probe-Cographen,Diplomarbeit,Uni-
versit¨a t Rostock,Institut f¨u r Informatik(2006).
2.David B.Chandler,Maw-Shang Chang,Anthonius J.J.Kloks,Jiping Liu,and
Sheng-Lung Peng,Recognition of probe cographs and partitioned probe distance hereditary graphs,Proceedings of AAIM2006,Lecture Notes in Computer Science 4041(2006)267-278.
3.Maw-Shang Chang,Anthonius J.J.Kloks,Dieter Kratsch,Jiping Liu,and Sheng-
Lung Peng,On the recognition of probe graphs of some self-complementary classes of perfect graphs,Proceedings COCOON2005,Lecture Notes in Computer Science 3595(2005)808-817.
4.Derek G.Corneil,Y.Perl,L.Stewart,A linear recognition algorithm for cographs,
SIAM J.Computing14(1985)926-934.
5.M.Hujter,Zs.Tuza,Precoloring extensions III:Classes of perfect graphs,Comb.
Prob.Comp.5(1996)35-56.
6.Information System on Graph Classes and their Inclusions(ISGCI),
wwwteo.informatik.uni-rostock.de/isgci
7.Van Bang Le,A good characterization of cograph contractions,J.Graph Theory
30(1999)309-318.
发布评论