Embedded Files
About the course
Among the most successful research approaches in graph theory and graph algorithms have been the study of sparse graphs. Among those, planar graphs have been historically one of the most studied graph classes due to their numerous real-world applications, dating back to the works of Euler and the celebrated four-color conjecture/theorem. Another type of sparse graphs are graphs of bounded treewidth, which have enormous applications not only in structural graph theory, but also in providing efficient algorithms for many computational problems on graphs and, more generally, any kind of discrete structure due to the celebrated Courcelle’s theorem.
However, planar graphs and graphs of bounded treewidth form (seemingly) somewhat orthogonal graph classes, since planar graphs can have arbitrarily large treewidth and graphs of treewidth 3 may be non-planar. A common generalization of these classes has been studied under the umbrella of graph minors, leading to the deep and complex theory of minor-closed graph classes by Robertson and Seymour.
In the last 20 years, these efforts have been further extended, which led to a comprehensive theory of sparse graphs, especially thanks to the efforts of Nešetřil and Ossona de Mendez, with the publication of the influential book titled ''Sparsity'', on the topic in 2012. In this theory, many properties of minor-closed graph classes are generalized through the concept of shallow minors and the definition of graphs of bounded expansion.
In this course, we will start by exposing the fundamental structural properties of graphs of bounded treewidth, planar graphs, and show how to generalize these properties to graph classes of bounded expansion.
Course details
The course is to be conducted in a completely offline mode with 24 hours of lectures and 24 hours of tutorials.
A certificate of participation will be given to all.
An examination will be conducted on the last day of the workshop and qualified candidates will be provided a certificate.
For PhD students enrolled in Indian institutes, this course is equivalent to 6 credits of coursework. This is valid only for those candidates who register and pass the examination.
Syllabus
Introduction and motivation, basics of graph theory, k-trees, treewidth, equivalence treewidth k / partial k-trees, basic properties, Brambles and duality theorem for treewidth, Dynamic programming for trees and graphs of bounded treewidth, Computing tree-decompositions, nice tree-decompositions, Courcelles’s theorem, related parameters (pathwidth, feedback vertex/edge set, vertex cover number, tree-depth, clique-width), Planar graphs: Euler's formula, number of edges and degeneracy via discharging, coloring planar graphs, Treewidth of planar graphs. Application to FPT algorithms and approximation algorithms, extension to bounded local treewidth, Subdivisions and minors, Kuratowski/Wagner theorems, planarity testing, minor-closed graph classes, Shallow minors, greatest reduced average degree, graph classes of bounded expansion, Generalized coloring numbers, algorithmic applications, Neighborhood complexity, VC-dimension, applications to locating-dominating sets and metric dimension, Low tree-depth colorings and applications to FPT algorithms, FO model checking, nowhere dense graphs, structured dense graph classes (clique-width, twin-width, flip-width) .
Objectives
Teaching the fundamental properties of graph classes of bounded treewidth, planar graphs, and graphs of bounded expansion.
Illustrate the usefulness of these graph classes by concrete algorithmic applications.
Give the students the opportunity to apply the exposed techniques during the tutorials.
Give perspectives to more general graph classes and graph parameters: nowhere dense graphs, and structured classes of dense graphs (via e.g. twin-width and clique-width).
Who can attend
The primary target participants are Ph.D. students from Mathematics or Computer Science or related departments whose research interest lies in graph theory and graph algorithms. This course may lead to research projects and collaborations.
Advanced Masters (M.Sc./M.Tech. or equivalent) students with a particular interest and background in graph theory and algorithms are also encouraged to participate.
Interested faculty members from reputed academic institutions and technical institutions are also regarded as potential participants.
Note: The number of student participants will be limited to 50.
Registration
Registration link: https://forms.gle/4MaACrHDhYwQ29jC9
Note: After you register, selected candidates will be notified by email, and upon payment of the registration fees, their candidature will be confirmed. Payment related details will be included in the selection notification email.
Registration fee
Students/Postdocs: 2000 INR (4 shared hostel accommodation included)
Students/Postdocs: 1000 INR (accommodation not included)
Faculty/Industry professional: 2500 INR (accommodation not included)
Food can be availed at IIT Dharwad on a payment basis (details to be updated soon).
Note: There is no central registration on the GIAN portal (gian.iith.ac.in); registration will be managed directly by the hosting institute. The registration fee to be paid upon receiving the selection notification email.
Processing charge for examination: 200 INR (only for those who register for examination)*
*Can be paid on or before 28th February 2025.
Important dates
Last date for registration: 31 January 2025
Notification of selection: 7 February 2025
Course duration: 24 February 2025 - 7 March 2025
Information brochure: Click here to download.
Additional information
eVISA application (international participants): https://indianvisaonline.gov.in/evisa/tvoa.html
*The workshop/course will be OFFLINE only.
Page updated
Google Sites
Report abuse