### Abstract

In the Maximum Subset Matching problem, which generalizes the maximum matching problem, we are given a graph G = (V, E) and S ⊂ V. The goal is to determine the maximum number of vertices of S that can be matched in a matching of G. Our first result is a new randomized algorithm for the Maximum Subset Matching problem that improves upon the fastest known algorithms for this problem. Our algorithm runs in Ṏ(ms^{(ω-1)/2}) time if m > s^{(ω+1)/2} and in Õ(s^{ω}) time if m < s^{(ω+1)/2}, where ω < 2.376 is the matrix multiplication exponent, m is the number of edges from S to V \ S, and s = |S|. The algorithm is based, in part, on a method for computing the rank of sparse rectangular integer matrices. Our second result is a new algorithm for the All-Pairs Shortest Paths (APSP) problem. Given an undirected graph with n vertices, and with integer weights from (1,...,W) assigned to its edges, we present an algorithm that solves the APSP problem in Õ(Wn ^{ω(1,1,μ)}) time where n^{μ} = vc(G) is the vertex cover number of G and ω(1, 1, μ) is the time needed to compute the Boolean product of an n × n matrix with an n × n^{μ} matrix. Already for the unweighted case this improves upon the previous O(n ^{2+μ}) and Õ(n^{ω}) time algorithms for this problem. In particular, if a graph has a vertex cover of size O(n ^{0.29}) then APSP in unweighted graphs can be solved in asymptotically optimal Õ(n^{2}) time, and otherwise it can be solved in O(n ^{1.844}vc(G)^{0.533}) time. The common feature of both results is their use of algorithms developed in recent years for fast (sparse) rectangular matrix multiplication.

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

Title of host publication | Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 175-186 |

Number of pages | 12 |

ISBN (Print) | 9783540755197 |

DOIs | |

State | Published - Jan 1 2007 |

Externally published | Yes |

Event | 15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israel Duration: Oct 8 2007 → Oct 10 2007 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4698 LNCS |

### Other

Other | 15th Annual European Symposium on Algorithms, ESA 2007 |
---|---|

Country | Israel |

City | Eilat |

Period | 10/8/07 → 10/10/07 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Fast algorithms for maximum subset matching and all-pairs shortest paths in graphs with a (not so) small vertex cover'. Together they form a unique fingerprint.

## Cite this

*Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings*(pp. 175-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4698 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-75520-3_17