{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/140045"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/140045","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Algorithms and Hardness for Approximating the Diameter of a Graph","abstract":"The diameter of a graph is one of the most basic and fundamental attributes of a graph. It is defined as the distance between the pair of vertices that is the farthest apart. The diameter of a graph is a meaningful parameter for many applications such as distributed computation and social networks. We seek fast algorithms for computing the diameter of a graph. This is one of the central problems in the area of fine-grained complexity. The naive algorithm for computing the diameter of a graph is to find the distance between all pairs of vertices and return the largest one. Interestingly, no better algorithm is known. Furthermore, there is evidence from fine-grained complexity, that no subquadratic time algorithm exists for computing the diameter of a graph exactly. In particular, such an algorithm would falsify the Strong Exponential Time Hypotehsis (SETH). For applications with very large graphs, even quadratic time can be prohibitively slow. Thus, we turn to approximation algorithms with faster running times. Prior work establishes a hierarchy of algorithms that trade-off time and accuracy, as well as a single lower bound conditioned on SETH. Our first main contribution is the development of a hierarchy of conditional lower bounds under SETH for approximating the diameter of a graph, that establish a time vs. accuracy trade-off. These lower bounds show that several of the known algorithms on the trade-off curve are conditionally tight. Second, we study the approximability of the diameter of a graph in a variety of natural settings, such as when the graph is changing over time, or when we only care about the distances between particular subsets of vertices, or when we only care about one-way distances in a directed graph. For these variants, we develop both approximation algorithms and conditional lower bounds, that are often tight.","abstract_html":"The diameter of a graph is one of the most basic and fundamental attributes of a graph. It is defined as the distance between the pair of vertices that is the farthest apart. The diameter of a graph is a meaningful parameter for many applications such as distributed computation and social networks. We seek fast algorithms for computing the diameter of a graph. This is one of the central problems in the area of fine-grained complexity. The naive algorithm for computing the diameter of a graph is to find the distance between all pairs of vertices and return the largest one. Interestingly, no better algorithm is known. Furthermore, there is evidence from fine-grained complexity, that no subquadratic time algorithm exists for computing the diameter of a graph exactly. In particular, such an algorithm would falsify the Strong Exponential Time Hypotehsis (SETH). For applications with very large graphs, even quadratic time can be prohibitively slow. Thus, we turn to approximation algorithms with faster running times. Prior work establishes a hierarchy of algorithms that trade-off time and accuracy, as well as a single lower bound conditioned on SETH. Our first main contribution is the development of a hierarchy of conditional lower bounds under SETH for approximating the diameter of a graph, that establish a time vs. accuracy trade-off. These lower bounds show that several of the known algorithms on the trade-off curve are conditionally tight. Second, we study the approximability of the diameter of a graph in a variety of natural settings, such as when the graph is changing over time, or when we only care about the distances between particular subsets of vertices, or when we only care about one-way distances in a directed graph. For these variants, we develop both approximation algorithms and conditional lower bounds, that are often tight.","abstract_has_math":false,"creators":["Wein, Nicole Spence"],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Williams, Virginia Vassilevska"],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09","date_published":"2021-09","updated_at":"2026-07-22T22:22:09Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/140045","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Williams, Virginia Vassilevska"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Wein, Nicole Spence"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-02-07T15:20:50Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-02-07T15:20:50Z"]},{"key":"dc:date.issued","label":"Date","values":["2021-09"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral","Doctor of Philosophy"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/140045"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The diameter of a graph is one of the most basic and fundamental attributes of a graph. It is defined as the distance between the pair of vertices that is the farthest apart. The diameter of a graph is a meaningful parameter for many applications such as distributed computation and social networks. We seek fast algorithms for computing the diameter of a graph. This is one of the central problems in the area of fine-grained complexity. The naive algorithm for computing the diameter of a graph is to find the distance between all pairs of vertices and return the largest one. Interestingly, no better algorithm is known. Furthermore, there is evidence from fine-grained complexity, that no subquadratic time algorithm exists for computing the diameter of a graph exactly. In particular, such an algorithm would falsify the Strong Exponential Time Hypotehsis (SETH). For applications with very large graphs, even quadratic time can be prohibitively slow. Thus, we turn to approximation algorithms with faster running times. Prior work establishes a hierarchy of algorithms that trade-off time and accuracy, as well as a single lower bound conditioned on SETH. Our first main contribution is the development of a hierarchy of conditional lower bounds under SETH for approximating the diameter of a graph, that establish a time vs. accuracy trade-off. These lower bounds show that several of the known algorithms on the trade-off curve are conditionally tight. Second, we study the approximability of the diameter of a graph in a variety of natural settings, such as when the graph is changing over time, or when we only care about the distances between particular subsets of vertices, or when we only care about one-way distances in a directed graph. For these variants, we develop both approximation algorithms and conditional lower bounds, that are often tight."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Algorithms and Hardness for Approximating the Diameter of a Graph"]}]}],"canonical_facts":{"dc:contributor.advisor":["Williams, Virginia Vassilevska"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Wein, Nicole Spence"],"dc:date.accessioned":["2022-02-07T15:20:50Z"],"dc:date.available":["2022-02-07T15:20:50Z"],"dc:date.issued":["2021-09"],"dc:description.abstract":["The diameter of a graph is one of the most basic and fundamental attributes of a graph. It is defined as the distance between the pair of vertices that is the farthest apart. The diameter of a graph is a meaningful parameter for many applications such as distributed computation and social networks. We seek fast algorithms for computing the diameter of a graph. This is one of the central problems in the area of fine-grained complexity. The naive algorithm for computing the diameter of a graph is to find the distance between all pairs of vertices and return the largest one. Interestingly, no better algorithm is known. Furthermore, there is evidence from fine-grained complexity, that no subquadratic time algorithm exists for computing the diameter of a graph exactly. In particular, such an algorithm would falsify the Strong Exponential Time Hypotehsis (SETH). For applications with very large graphs, even quadratic time can be prohibitively slow. Thus, we turn to approximation algorithms with faster running times. Prior work establishes a hierarchy of algorithms that trade-off time and accuracy, as well as a single lower bound conditioned on SETH. Our first main contribution is the development of a hierarchy of conditional lower bounds under SETH for approximating the diameter of a graph, that establish a time vs. accuracy trade-off. These lower bounds show that several of the known algorithms on the trade-off curve are conditionally tight. Second, we study the approximability of the diameter of a graph in a variety of natural settings, such as when the graph is changing over time, or when we only care about the distances between particular subsets of vertices, or when we only care about one-way distances in a directed graph. For these variants, we develop both approximation algorithms and conditional lower bounds, that are often tight."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/140045"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Algorithms and Hardness for Approximating the Diameter of a Graph"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral","Doctor of Philosophy"]},"updated_at":"2026-07-22T22:22:09Z"}