Advanced Topics Graph AlgorithmsAdvanced Topics in Graph AlgorithmsFedor V. Fomin Paderborn 2002Advanced Topics Graph AlgorithmsLecture 1What is this course about?Advanced Topics Graph AlgorithmsWhat this course is about?GraphsAdvanced Topics Graph AlgorithmsWhat this course is about?Graphs?Problems on graphsAdvanced Topics Graph AlgorithmsWhat this course is about?Graphs?Problems on graphs?Algorithms to solve these problemsAdvanced Topics Graph AlgorithmsGraphsAdvanced Topics Graph AlgorithmsGraphsAdvanced Topics Graph AlgorithmsProblems?Graph coloring Advanced Topics Graph AlgorithmsMaximum clique sizeAdvanced Topics Graph AlgorithmsIndependent setAdvanced Topics Graph AlgorithmsWhat properties of a graph can be useful to solve the problem?Advanced Topics Graph AlgorithmsBasics. Graph TheoryAdvanced Topics Graph AlgorithmsPath PCycle CIf is a path, the graph obtained from P by addingis cycleAdvanced Topics Graph AlgorithmsAdvanced Topics Graph AlgorithmsSome special graphs?Complete graph Kn?Trees?Bipartite graph?Complete bipartite graphAdvanced Topics Graph AlgorithmsCliqueAdvanced Topics Graph AlgorithmsAlgorithms?We say that an algorithm for problem runs in time O(f(n) if for some constant c there exists an implementation of A which terminates after at most O(f(n) computational steps for all instances of size n.Advanced Topics Graph AlgorithmsLinear time algorithmAdvanced Topics Graph AlgorithmsHow to represent a graph?Adjacency list?Adjacency matrixAdvanced Topics Graph AlgorithmsExample of linear problem:converting the adjacency list of a graph into sorted adjacency lists.Advanced Topics Graph AlgorithmsAdvanced Topics Graph AlgorithmsBuck sortingAdvanced Topics Graph AlgorithmsBuck sortingAdvanced Topics Graph AlgorithmsBuck sorting?Buck sorting takes O(n+di) timeAdvanced Topics Graph AlgorithmsAlgorithmAdvanced Topics Graph AlgorithmsTheorem?Algorithm Sorting the Adjacency Lists of Sorting the Adjacency Lists of GraphsGraphs runs in O(m+n)time. Advanced Topics Graph AlgorithmsProof:Advanced Topics Graph AlgorithmsAnother examples?Testing planarity, connectivity, biconnectivityAdvanced Topics Graph AlgorithmsNP complete problemsAdvanced Topics Graph AlgorithmsPart 1. Perfect graphsAdvanced Topics Graph AlgorithmsClique and ISAdvanced Topics Graph AlgorithmsColouringAdvanced Topics Graph AlgorithmsDefinition of perfect graphsAdvanced Topics Graph AlgorithmsExamples of perfect graphs?Bipartite graphs?Cliques?Odd cycle - NOT?More examples to appear laterAdvanced Topics Graph AlgorithmsExample: Integer programmingDefineandAdvanced Topics Graph AlgorithmsExample: Integer programming# of IS containigisAdvanced Topics Graph AlgorithmsExampleAdvanced Topics Graph AlgorithmsExampleThe dualAdvanced Topics Graph AlgorithmsExampleAdvanced Topics Graph AlgorithmsExampleIf graph is perfect Advanced Topics Graph AlgorithmsExample: Final remarkFor linear programming (solution is not necessarily integer) the value of an optimal solution of the primal is equal to the value of an optimal solution of the dual. Stating graph problems as linear programming problem leads to an interesting field: fractional graph theory. In fractional graph theory it is possible that the fractional chromatic number is not integer but it should be equal to fractional clique number!Advanced Topics Graph AlgorithmsChapter I. CHORDAL GRAPHSCHORDAL GRAPHS PLAY VERY IMPORTANT ROLE IN OUR COURSE.Advanced Topics Graph AlgorithmsDefinition of chordal graph?A chord of a cycle Cis an edge not in Cthat has endpoints in C?A chordless cycle in Gis a cycle of length more than three that has no chord.?A graph Gis chordal if it does not contain a chordless cycle. Advanced Topics Graph AlgorithmsSimlicial vertex: definitionAdvanced Topics Graph AlgorithmsHereditary property?Exercise: Prove that chordality is hereditary property. (In other words, every induced subgraph of a chordal graph is chordal.)Advanced Topics Graph AlgorithmsWe shall prove that every chordal graph has a simplicial vertex. Since chordality is hereditary property, this implies the following naive algorithm of testing chordality of a graph G: o While there are simplicial vertices do o Find a simplicial vertex and remove it o If the resulting graph is empty thenGis chordal o Else G is not chordalAdvanced Topics Graph AlgorithmsRunning time of the naive algorithmAdvanced Topics Graph AlgorithmsPE-ordering definitionVertex ordering of a graph G=(V,E) is a PE-ordering(perfect elimination ordering) if for everyvertex viis simplicial in the graph induced by vertex set Advanced Topics Graph AlgorithmsMinimal separators?A subset S of vertices of a connected graph G is called an a,b- separator for non adjacent vertices a and b in V(G) S if a and b are in different connected component of the subgraph of G induced by V(G) S.?If no proper subset of an a,b-separator S separates a and b in this way, then S is called aminimal a