Organizing Committee
- Erik Demaine
Massachusetts Institute of Technology - Daniel Marx
Hungarian Academy of Sciences (MTA) - Blair Sullivan
North Carolina State University
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
Talks will be presented virtually or in-person as indicated in the schedule below.
- Speaker
- Poster Presenter
- Attendee
- Virtual Attendee
-
Aaron Adcock
Stanford University
-
Yixin Cao
Hungarian Academy of Sciences (MTA)
-
Rajesh Chitnis
University of Maryland
-
Erik Demaine
Massachusetts Institute of Technology
-
Hossein Esfandiari
University of Maryland
-
Fedor Fomin
University of Bergen
-
Kyle Fox
University of Illinois at Urbana-Champaign
-
MohammadTaghi Hajiaghayi
University of Maryland
-
Philip Klein
Brown University
-
Michael Langston
University of Tennessee
-
Vahid Liaghat
University of Maryland
-
Daniel Lokshtanov
University of Bergen
-
Daniel Marx
Hungarian Academy of Sciences (MTA)
-
Morteza Monemizadeh
University of Maryland
-
Shay Mozes
Interdisciplinary Center for Neural Computation at Hebrew University
-
Michael O'Brien
North Carolina State University
-
Felix Reidl
RWTH Aachen
-
Fernando Sanchez Villaamil
RWTH Aachen
-
Saket Saurabh
Institute of Mathematical Sciences
-
Aaron Schild
Princeton University
-
Aikaterini Sotiraki
Massachusetts Institute of Technology
-
Blair Sullivan
North Carolina State University
-
Ali Vakilian
Massachusetts Institute of Technology
Workshop Schedule
Thursday, April 24, 2014
Time | Event | Location | Materials |
---|---|---|---|
8:30 - 9:00am EDT | Registration | 11th Floor Collaborative Space | |
9:00 - 10:20am EDT | Basic techniques of fixed-parameter tractability (Part 1) - Saket Saurabh, Institute of Mathematical Sciences | 11th Floor Lecture Hall | |
10:30 - 11:00am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
11:00 - 12:30pm EDT | Basic techniques of fixed-parameter tractability (Part 2) - Daniel Lokshtanov, University of Bergen | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Kernelization - Saket Saurabh, Institute of Mathematical Sciences | 11th Floor Lecture Hall | |
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research |
Friday, April 25, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:20am EDT | Treewidth and applications - Fedor Fomin, University of Bergen | 11th Floor Lecture Hall | |
10:30 - 10:45am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
10:45 - 11:15am EDT | Open Problem Session | 11th Floor Lecture Hall | |
11:15 - 12:45pm EDT | Minors and Algorithms - Erik Demaine, Massachusetts Institute of Technology | 11th Floor Lecture Hall | |
12:45 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research |
Saturday, April 26, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:20am EDT | Approximation Algorithms - Mohammad Taghi Hajiaghayi, University of Maryland | 11th Floor Lecture Hall | |
10:30 - 11:00am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
11:00 - 12:30pm EDT | Lower bounds - Daniel Marx, Hungarian Academy of Sciences (MTA) | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research |
Sunday, April 27, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:20am EDT | Separators - Daniel Marx, Hungarian Academy of Sciences (MTA) | 11th Floor Lecture Hall | |
10:30 - 11:00am EDT | Coffee/Tea Break | ||
11:00 - 12:30pm EDT | Connecting to the Real-World Applications - Blair Sullivan, North Carolina State University | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | ||
4:00 - 5:00pm EDT | Research |
Monday, April 28, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:15am EDT | Opening Session | 11th Floor Lecture Hall | |
10:15 - 10:45am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
10:45 - 12:00pm EDT | Research | ||
12:00 - 12:30pm EDT | Problem Session Update | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research | ||
5:00 - 5:30pm EDT | Problem Session Update | 11th Floor Lecture Hall |
Tuesday, April 29, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:15am EDT | Research | ||
10:15 - 10:45am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
10:45 - 12:00pm EDT | Research | ||
12:00 - 12:30pm EDT | Problem Session Update | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research | ||
5:00 - 5:30pm EDT | Problem Session Update | 11th Floor Lecture Hall |
Wednesday, April 30, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:15am EDT | Research | ||
10:15 - 10:45am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
10:45 - 12:00pm EDT | Research | ||
12:00 - 12:30pm EDT | Problem Session Update | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research | ||
5:00 - 5:30pm EDT | Problem Session Update | 10th floor classroom |
Thursday, May 1, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:15am EDT | Research | ||
10:15 - 10:45am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
10:45 - 12:00pm EDT | Research | ||
12:00 - 12:30pm EDT | Problem Session Update | 11th Floor Lecture Hall | |
12:30 - 2:00pm EDT | Break for Lunch | ||
2:00 - 3:30pm EDT | Research | ||
3:30 - 4:00pm EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
4:00 - 5:00pm EDT | Research | ||
5:00 - 5:30pm EDT | Problem Session Update | 11th Floor Lecture Hall |
Friday, May 2, 2014
Time | Event | Location | Materials |
---|---|---|---|
9:00 - 10:15am EDT | Research | ||
10:15 - 10:45am EDT | Coffee/Tea Break | 11th Floor Collaborative Space | |
10:45 - 12:00pm EDT | Research | ||
12:00 - 12:30pm EDT | Problem Session Update | 11th Floor Collaborative Space | |
12:30 - 2:30pm EDT | Break for Lunch | ||
2:30 - 5:00pm EDT | Closing Session/Wrap-Up | 11th Floor Lecture Hall |