Graph Classes A Survey

1、Graph ClassesA Survey,張貿翔 中正大學資訊工程學系,Meeting Room Reservation,One meeting room Reservation: Gary10:0011:00 Mary10:3012:00 Jones13:3014:30 Amy14:0015:30 David11:0012:30 Tom12:0014:30 To satisfy as many as possible,The conflict graph,The maximum Independent Set Problem in Graphs,An independent set Ano

2、ther independent set A maximum independent set ,The meeting room reservation problem is reduced to the maximum independent set problem in graphs. The maximum independent set problem in general graphs is NP-hard. Most of optimization problems in graphs are NP-hard. It turns out that the conflict grap

3、h of a meeting room reservation problem is an interval graph. The maximum independent set problem can be solved in O(n) time in interval graphs if end vertices are sorted.,Graph Classes,A graph is called a graph if it satisfies property . For example, a graph having no induced cycle of length greate

4、r than 3 is called a chordal graph.,4,A chord of cycle 5, 7, 8, 6, 4, 5.,Interval graphs,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,Circle Graphs,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,Planar Graphs,K5 and K3,3 are not planar graphs.,Too many graph classes,There are almost 200 graph classes described in the book “Gra

5、ph Classes, A Survey” by Brandstdt, Le, and Spinrad, published in 1999. D. S. Johnson remarked that “many graph theorists have made careers out of inventing and characterizing new classes of graphs; there are by now far too many classes for a single column to survey.” in “The NP-completeness column:

6、 an ongoing guide, J. Algorithm, 6 (1985).,Distance-Hereditary,Some Graph Classes,The Interval graph Recognition Problem,Given a graph G,test whether there exists an interval model.,官兵捉強盜,The Graph Searching Problem,The graph searching problem is a graph-theoretical game played on an undirected grap

7、h considered as a system of tunnels in which all the tunnels are initially contaminated by a gas. There are three kinds of moves in edge searching: (1) placing a searcher on a vertex; (2) removing a searcher from a vertex; and (3) clear an edge by either (3.1) moving a searcher from one vertex to an

8、other along an edge or (3.2) placing two searchers on the two endpoints of the edge. A cleared edge may be recontaminated once there is a path without any searchers connecting the edge with a contaminated one. The goal of this game is to discover a sequence of moves, called strategy , clear the grap

9、h with the least number of searchers.,The Graph Searching Problem (Cont.),The graph searching problem is polynomial-time solvable on interval graphs and split graphs, etc.,Longest Increasing Subsequences,Input: a sequence, 12, 3, 10, 9, 8, 13, 14, 1, 11. Output: a longest subsequence Subsequences: 3

10、, 10, 9 or 10, 13, 14 etc. Increasing subsequences: 3, 8, 11 or 12, 13, 14, or 3, 10, 13, 14 Longest increasing subsequence: 3, 10, 13, 14 or 3, 9, 13, 14 etc.,12, 3, 10, 9, 8, 13, 14, 1, 11,(1, 12), (2, 3), (3, 10), (4, 9), (5,8), (6,13), (7,14), (8, 1), (9, 11),1,2,3,4,5,6,7,8,9,1,3,8,9,10,11,12,1

11、3,14,The longest increasing subsequence can be reduced to the maximum independent set problem in permutation graphs.,A permutation graph G,A matching diagram of G,An Approach to Designing Graph Algorithms,Most of problems in graphs are NP-hard. Many problems in graphs become polynomial-time solvable

12、 if the graphs considered satisfy some nice property . For example, the maximum independent set problem is NP-hard in general graphs but polynomial-time solvable in chordal graphs, interval graphs, and permutation graphs, etc.,Chromosome,Cut relatively small, random pieces of the chromosome. Run che

13、mical experiments on the small pieces to get accurate information about these. This allows researchers to get information about fragments and frequencies of types of fragments, but loss information about how the fragments are ordered on the chromosome. Each fragment should form an interval on the ch

14、romosome, it is natural to model this problem as an interval graph problem with fragments corresponding to vertices.,For this model to be useful, there must be a way to determine which fragments should overlap in the chromosome, corresponding to which vertices should be adjacent in the interval mode

15、l. Such tests have been developed, which makes it seem simple to use interval graph techniques to solve the gene reconstruction problem. The tests may produce errors.,Errors come in two forms: False positive: The tests say that fragments overlap when they do not. False negative: The tests say that f

16、ragments do not overlap when they really do. Depending on which test is used and what thresholds are set, false positives may be much more common that false negatives, much less common, or both may occur with relatively equal probability.,If we assume that all errors are false negatives, we want to

17、know the minimum number of edges we can add to make the graph interval graph. This problem is called the interval graph completion problem. If we assume all errors are false positives, we want to know the minimum number of overlaps we can delete from the test results to get an interval graph; this i

18、s called the maximum interval subgraph problem.,If errors can be false positives or false negatives, we want to minimize the number of edge deletions and additions so that the result is an interval graph; this is called the interval graph modification problem. Assume that there are no errors in the

19、tests. If we have n fragments, and we want to reconstruct the entire interval graph, the method described calls for (n2) chemical tests to determine whether fragments overlap.,A subset of the fragments are selected to be “probes”, and the remaining fragments are called nonprobes. Instead of testing

20、overlap relationships between pairs of fragments, tests are only made between a probe and another fragment. The overlap graph of fragments obtained in this way can be made into an interval graph by adding edges between some nonprobes.,The Partitioned Probe Graph Recognition Problem,A partitioned pro

21、be graph is a graph G = (V, E) where a subset of independent vertices are marked as “nonprobes”, and the remaining vertices are called probes. To determine whether a partitioned probe graph satisfies property .,The Partitioned probe Interval graph Recognition Problem,Given a partitioned graph G,test

22、 whether there exists a probe interval model.,where vertices 2, 4, 5 are nonprobes,Given a partitioned probe graph G,determine whether there exists a probe matching diagram for G.,The partitioned Probe Permutation graph Recognition Problem,where vertices 1, 6, 8, 9 are nonprobes,The Partitioned Prob

23、e Graph Recognition Problem,Given a partitioned probe graph G = (P + N, E), determine whether G is a partitioned probe graph, i.e., there exists a set N of edges such that the end vertices of every edge in N are nonprobes and (P + N, E + N ) is an graph.,The Unpartitioned Probe Graph Recognition Pro

24、blem,Given a graph G = (V, E), determine whether V can be partitioned into probes P and nonprobes N such that N is an independent set of G and G = (P + N, E) is a partitioned probe graph.,Current results on the recognition problems of some probe graph classes,P: Polynomial-time solvable ?: unknown,A

25、 connected graph is distance hereditary if the distance between every two vertices in any connected induced subgraph is the same as in the original graph.,A distance-hereditary graph,Distance-Hereditary Graphs,Distance-Hereditary Graphs,Two vertices x and y are true twins if Nx= Ny. Two vertices x a

26、nd y are false twins if N(x)= N(y) . Let G = (V, E) be a graph with |V| 1. Then G is distance hereditary if and only if G is obtained from an edge by a sequence of one-vertex extensions consisting of attaching pendant vertices and creating twins.,Distance-Hereditary Graphs,1,2,A one vertex extension sequence of G: 1,2,3,4,5,6,7,8,9,10,11,A distance-hereditary graph G,Recognition of Partitioned Prob