## Abstract

The aspect ratio of a (positively) weighted graph G is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest paths. Popular paradigms are to interpolate between the settings of weighted and unweighted input graphs by incurring a dependence on aspect ratio, or by simply restricting attention to input graphs of low aspect ratio. This paper studies the effects of these paradigms, investigating whether graphs of low aspect ratio have more structured shortest paths than graphs in general. In particular, we raise the question of whether one can generally take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths. Our findings are: Every weighted DAG on n nodes has a shortest-paths preserving graph of aspect ratio O(n). A simple lower bound shows that this is tight. The previous result does not extend to general directed or undirected graphs; in fact, the answer turns out to be exponential in these settings. In particular, we construct directed and undirected n-node graphs for which any shortest-paths preserving graph has aspect ratio 2ω(n). We also consider the approximate version of this problem, where the goal is for shortest paths in H to correspond to approximate shortest paths in G. We show that our exponential lower bounds extend even to this setting. We also show that in a closely related model, where approximate shortest paths in H must also correspond to approximate shortest paths in G, even DAGs require exponential aspect ratio.

Original language | English (US) |
---|---|

Title of host publication | 15th Innovations in Theoretical Computer Science Conference, ITCS 2024 |

Editors | Venkatesan Guruswami |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959773096 |

DOIs | |

State | Published - Jan 2024 |

Event | 15th Innovations in Theoretical Computer Science Conference, ITCS 2024 - Berkeley, United States Duration: Jan 30 2024 → Feb 2 2024 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 287 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 15th Innovations in Theoretical Computer Science Conference, ITCS 2024 |
---|---|

Country/Territory | United States |

City | Berkeley |

Period | 1/30/24 → 2/2/24 |

## Keywords

- Graph theory
- Shortest paths
- Weighted graphs

## ASJC Scopus subject areas

- Software