DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2022.9

Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs

Authors: Pierre Bergé, Guillaume Ducoffe, and Michel Habib

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

On sparse graphs, Roditty and Williams [2013] proved that no O(n^{2-ε})-time algorithm achieves an approximation factor smaller than 3/2 for the diameter problem unless SETH fails. We answer here an open question formulated in the literature: can we use the structural properties of median graphs to break this global quadratic barrier? We propose the first combinatorial algorithm computing exactly all eccentricities of a median graph in truly subquadratic time. Median graphs constitute the family of graphs which is the most studied in metric graph theory because their structure represents many other discrete and geometric concepts, such as CAT(0) cube complexes. Our result generalizes a recent one, stating that there is a linear-time algorithm for computing all eccentricities in median graphs with bounded dimension d, i.e. the dimension of the largest induced hypercube (note that 1-dimensional median graphs are exactly the forests). This prerequisite on d is not necessarily anymore to determine all eccentricities in subquadratic time. The execution time of our algorithm is O(n^{1.6456}log^{O(1)} n).

Cite as

Pierre Bergé, Guillaume Ducoffe, and Michel Habib. Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{berge_et_al:LIPIcs.STACS.2022.9,
  author =	{Berg\'{e}, Pierre and Ducoffe, Guillaume and Habib, Michel},
  title =	{{Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.9},
  URN =		{urn:nbn:de:0030-drops-158192},
  doi =		{10.4230/LIPIcs.STACS.2022.9},
  annote =	{Keywords: Diameter, Eccentricities, Metric graph theory, Median graphs, Hypercubes}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.43

Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Authors: Michel Habib and Lalla Mouatadid

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

We study the maximum induced matching problem on a graph G. Induced matchings correspond to independent sets in L^2(G), the square of the line graph of G. The problem is NP-complete on bipartite graphs. In this work, we show that for a number of graph families with forbidden vertex orderings, almost all forbidden patterns on three vertices are preserved when taking the square of the line graph. These orderings can be computed in linear time in the size of the input graph. In particular, given a graph class \mathcal{G} characterized by a vertex ordering, and a graph G=(V,E) \in \mathcal{G} with a corresponding vertex ordering \sigma of V, one can produce (in linear time in the size of G) an ordering on the vertices of L^2(G), that shows that L^2(G) \in \mathcal{G} - for a number of graph classes \mathcal{G} - without computing the line graph or the square of the line graph of G. These results generalize and unify previous ones on showing closure under L^2(\cdot) for various graph families. Furthermore, these orderings on L^2(G) can be exploited algorithmically to compute a maximum induced matching on G faster. We illustrate this latter fact in the second half of the paper where we focus on cocomparability graphs, a large graph class that includes interval, permutation, trapezoid graphs, and co-graphs, and we present the first \mathcal{O}(mn) time algorithm to compute a maximum weighted induced matching on cocomparability graphs; an improvement from the best known \mathcal{O}(n^4) time algorithm for the unweighted case.

Cite as

Michel Habib and Lalla Mouatadid. Maximum Induced Matching Algorithms via Vertex Ordering Characterizations. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 43:1-43:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{habib_et_al:LIPIcs.ISAAC.2017.43,
  author =	{Habib, Michel and Mouatadid, Lalla},
  title =	{{Maximum Induced Matching Algorithms via Vertex Ordering Characterizations}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{43:1--43:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.43},
  URN =		{urn:nbn:de:0030-drops-82178},
  doi =		{10.4230/LIPIcs.ISAAC.2017.43},
  annote =	{Keywords: Maximum induced matching, Independent set, Vertex ordering charac- terization, Graph classes, Fast algorithms, Cocomparability graphs}
}

Search Results

Documents authored by Habib, Michel

Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs

Abstract

Cite as

Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Abstract

Cite as

Thanks for your feedback!

Could not send message