Organizing Committee
Abstract

This working group will develop new theoretically grounded approaches to practical problems on graphs and networks using the arsenal of graph structure theory and algorithms (treewidth, minors, fixed-parameter tractability, approximation algorithms, etc.).

Our approach is to combine the expertise of a mix of junior and senior researchers from three disciplines: mathematics (graph theory), computer science (fixed-parameter and approximation algorithms), and applied network analysis (social networks, power grid, bioinformatics, etc.). During this research cluster, we will identify specific practically motivated problems, and tackle the key associated mathematical challenges, with a goal of ultimately encouraging broader adoption of graph-structure-based tools in the computational community. This goal is particularly important given the emergence of vast quantities of relational data (a.k.a. networks) and increased need for analysis via scalable algorithms.

We face several challenges in making graph structure techniques applicable to real-world network analysis. First, many of the algorithms currently involve incredibly large constants (e.g., in their dependence on an excluded minor), so a natural goal is to improve or replace the relevant components with more reasonable dependencies. Second, we do not know which real-world networks fall into one or more of the mathematical graph classes where structural techniques are applicable. This problem can be tackled mathematically, through generative models, or experimentally, raising several questions about how to test whether specific graphs belong to parametrically defined classes. This problem becomes even more interesting when one considers that real-world networks are generally noisy, which means that the observed graph may have extra edges that place it outside the desired class, even if the intrinsic network satisfies the necessary conditions. For graphs that are "nearly" within a tractable graph class, can we detect which parts need modification to apply the efficient algorithms, and bound the effect of these modifications on the computed solution? We are excited by the new theoretical challenges raised by these practical questions, as well as the potential for significantly impacting the computability of many quantities of interest on real-world graphs.

Confirmed Speakers & Participants

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Thursday, April 24, 2014
TimeEventLocationMaterials
8:30 - 9:00am EDTRegistration11th Floor Collaborative Space 
9:00 - 10:20am EDTBasic techniques of fixed-parameter tractability (Part 1) - Saket Saurabh, Institute of Mathematical Sciences11th Floor Lecture Hall 
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 12:30pm EDTBasic techniques of fixed-parameter tractability (Part 2) - Daniel Lokshtanov, University of Bergen11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTKernelization - Saket Saurabh, Institute of Mathematical Sciences11th Floor Lecture Hall 
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
Friday, April 25, 2014
TimeEventLocationMaterials
9:00 - 10:20am EDTTreewidth and applications - Fedor Fomin, University of Bergen11th Floor Lecture Hall 
10:30 - 10:45am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:45 - 11:15am EDTOpen Problem Session11th Floor Lecture Hall 
11:15 - 12:45pm EDTMinors and Algorithms - Erik Demaine, Massachusetts Institute of Technology11th Floor Lecture Hall 
12:45 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
Saturday, April 26, 2014
TimeEventLocationMaterials
9:00 - 10:20am EDTApproximation Algorithms - Mohammad Taghi Hajiaghayi, University of Maryland11th Floor Lecture Hall 
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 12:30pm EDTLower bounds - Daniel Marx, Hungarian Academy of Sciences (MTA)11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
Sunday, April 27, 2014
TimeEventLocationMaterials
9:00 - 10:20am EDTSeparators - Daniel Marx, Hungarian Academy of Sciences (MTA)11th Floor Lecture Hall 
10:30 - 11:00am EDTCoffee/Tea Break  
11:00 - 12:30pm EDTConnecting to the Real-World Applications - Blair Sullivan, North Carolina State University11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break  
4:00 - 5:00pm EDTResearch  
Monday, April 28, 2014
TimeEventLocationMaterials
9:00 - 10:15am EDTOpening Session11th Floor Lecture Hall 
10:15 - 10:45am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:45 - 12:00pm EDTResearch  
12:00 - 12:30pm EDTProblem Session Update11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
5:00 - 5:30pm EDTProblem Session Update11th Floor Lecture Hall 
Tuesday, April 29, 2014
TimeEventLocationMaterials
9:00 - 10:15am EDTResearch  
10:15 - 10:45am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:45 - 12:00pm EDTResearch  
12:00 - 12:30pm EDTProblem Session Update11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
5:00 - 5:30pm EDTProblem Session Update11th Floor Lecture Hall 
Wednesday, April 30, 2014
TimeEventLocationMaterials
9:00 - 10:15am EDTResearch  
10:15 - 10:45am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:45 - 12:00pm EDTResearch  
12:00 - 12:30pm EDTProblem Session Update11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
5:00 - 5:30pm EDTProblem Session Update10th floor classroom 
Thursday, May 1, 2014
TimeEventLocationMaterials
9:00 - 10:15am EDTResearch  
10:15 - 10:45am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:45 - 12:00pm EDTResearch  
12:00 - 12:30pm EDTProblem Session Update11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:30pm EDTResearch  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 5:00pm EDTResearch  
5:00 - 5:30pm EDTProblem Session Update11th Floor Lecture Hall 
Friday, May 2, 2014
TimeEventLocationMaterials
9:00 - 10:15am EDTResearch  
10:15 - 10:45am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:45 - 12:00pm EDTResearch  
12:00 - 12:30pm EDTProblem Session Update11th Floor Collaborative Space 
12:30 - 2:30pm EDTBreak for Lunch  
2:30 - 5:00pm EDTClosing Session/Wrap-Up11th Floor Lecture Hall 

Associated Semester Workshops

Network Science and Graph Algorithms
Image for "Network Science and Graph Algorithms"
Semidefinite Programming and Graph Algorithms
Image for "Semidefinite Programming and Graph Algorithms"
Stochastic Graph Models
Image for "Stochastic Graph Models"

Research Clusters