Fragments of Structural and Algorithmic Graph Theory

582755
1-2
Algoritmit ja koneoppiminen
Syventävät opinnot
In the course we will give an overview of a selection of topics in structural and algorithmic graph theory. Particular emphasis will be given to algorithmic and complexity issues.
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2015 syksy 01.09-04.09. 1-1 Englanti

Luennot

Aika Huone Luennoija Päivämäärä
Ti 16-18 B222 Martin Milanic 01.09.2015-04.09.2015
Ke 16-18 B222 Martin Milanic 01.09.2015-04.09.2015
To 16-18 B222 Martin Milanic 01.09.2015-04.09.2015
Pe 14-16 B222 Martin Milanic 01.09.2015-04.09.2015

Yleistä

This is a self-contained mini-course on graph theory, given by Prof. Martin Milanič, from the University of Primorska, in Koper, Slovenia. Prof. Milanič is visiting the Department of Computer Science in the week 31 August - 4 September, with an Erasmus Exchange for Teachers. The course can give up to 3 credits (see below Completing the course)

Graph theory is a relatively young branch of discrete mathematics that has been developing rapidly in the last decades, mostly due to its many applications in the modern world in fields as diverse as computer science, social sciences, biology and logistics. With (finite) graphs, one can model pairwise relations between entities such as computers, individuals, proteins in a cell and cities. In their mathematical abstraction, entities are usually referred to as vertices, and the fact that that two entities are related is represented by connecting two vertices by an edge.

One of the most fruitful applications of graph theory stems from its capability of modeling phenomena in static and dynamic interconnection networks, with application areas such as biology, epidemiology, sociology, economics, and computer science. In particular, practical and theoretical issues in computer science motivate a number of graph theoretic questions and concepts, including the independent set problem, the graph coloring problem, several variants of the dominating set problem, the problems of finding either dense or sparse substructures satisfying certain connectivity requirements, and the problems of designing efficient algorithms for combinatorial optimization problems arising in the design of optical networks.
In the course we will give an overview of a selection of topics in structural and algorithmic graph theory. Particular emphasis will be given to algorithmic and complexity issues.
 
The following is the list of topics that we expect to cover in the four lectures:
  1. Review of basic notions in graph theory, algorithms and complexity. Basic graph theoretic definitions. Graph represenatations. Classes P and NP, NP-hardness, polynomial reductions, 2-SAT problem, 3-SAT problem.
  2. Graph traversal algorithms and their applications. Breadth-first search. Application: A polynomial time algorithm for 2-SAT. Depth-first search. Application: topological sorting. Applications of 2-SAT to graph theory problems. Application of topological sorting: shortest paths in directed acyclic graphs.
  3. Graph colorings. Chromatic number, upper and lower bounds. Greedy algorithm and its analysis. The Four Color Theorem. Hadwiger's Conjecture. Brooks' Theorem. Edge colorings and Vizing's Theorem. List colorings. Galvin's Theorem. Algorithmic aspects of graph coloring. NP-completeness of the problem of computing the chromatic number. Applications in scheduling.
  4. Perfect graphs and their subclasses. Basic theory and examples of hereditary graph classes. Perfect graphs and their properties. Cographs. Split graphs and threshold graphs. Chordal graphs. Interval graphs. Efficient algorithms for various problems based on structural properties of graphs in these classes.

Kurssin suorittaminen

Attending all four lectures gives 1 credit. Solving the exercises handed out during the course gives at most 2 extra credits as follows. 

There will be 4 homework assignments, each with three problems. Students taking the course for 2 credits submit solutions to problems 1 and 2 (in each assignment). Students taking the course for 3 credits submit solutions to all problems. Partial grades will be given for partial solutions. There will be 12 points per problem, for a total of 96 (2 credits), resp. 144 points (3 credits).
 
The grading scheme will be as follows: 60-69%: grade 2, 70-79%: grade 3, 80-89%: grade 4, 90-100%: grade 5.
 
Contact details
 
For questions regarding course contents, contact martin.milanic@upr.si. For administrative questions, contact alexandru.tomescu@helsinki.fi.

Kirjallisuus ja materiaali

Course materials

  • Glossary of basic definitions
  • 1.9.2015 First lecture. The slides have been sent by e-mail. Here are the exercises for the first lecture.
  • 2.9.2015 Second Lecture. The slides have been sent by e-mail. Here are the exercises for the second lecture.
  • 3.9.2015 Third Lecture. Slides have been sent by e-mail. Extra slides have been sent by e-mail. Here are the exercises for the third lecture.
  • 4.9.2015 Fourth lecture. Slides have been sent by e-mail. Here are the exercises for the fourth lecture.

 

References

The course is based on several sources (books and research articles). The following is a list of some relevant literature:

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, second edition. McGraw-Hill, 2001.
  • M. R. Garey, D. S. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness, 1979.
  • M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, Volume 57 in the series Annals of Discrete Mathematics. North Holland, second edition, 2004.
  • A. Brandstädt, V. B. Le, J. P. Spinrad. Graph Classes: A Survey. SIAM, 1999.
  • V. V. Vazirani. Approximation Algorithms, Springer-Verlag, 2001.
  • J. A. Bondy, U. S. R. Murty. Graph Theory, North-Holland, Springer-Verlag, 2008.
  • B. Korte, J. Vygen. Combinatorial Optimization. Theory and Algorithms, Volume 21 in the series Algorithms and Combinatorics, Springer-Verlag, druga izdaja, 2002.
  • R. Diestel, Graph Theory. Springer, 2006.
  • A. Schrijver, Combinatorial Optimization, Springer, 2003.