The enumeration of all subgraphs respecting some structural property is a fundamental task in theoretical computer science, with practical applications in many branches of data mining and network analysis. It is often of interest to only consider solutions (subgraphs) that are maximal under inclusion, and to achieve output-sensitive complexity, i.e., bounding the running time with respect to the number of subgraphs produced. In this paper, we provide a survey of techniques for designing output-sensitive algorithms for subgraph enumeration, including partition-based approaches such as flashlight search, solution-graph traversal methods such as reverse search, and cost amortization strategies such as push-out amortization. We also briefly discuss classes of efficiency, hardness of enumeration, and variants such as approximate enumeration. The paper is meant as an accessible handbook for learning the basics of the field and as a practical reference for selecting state-of-the-art subgraph enumeration strategies fitting to one’s needs.

Designing Output Sensitive Algorithms for Subgraph Enumeration / Conte A., Kurita K., Marino A., Punzi G., Uno T., Wasa K.. - ELETTRONICO. - 132:(2025), pp. 1-40. (From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 2025 ita 2025) [10.4230/OASIcs.Grossi.2025.19].

Designing Output Sensitive Algorithms for Subgraph Enumeration

Kurita K.;Marino A.;Uno T.;Wasa K.
2025

Abstract

The enumeration of all subgraphs respecting some structural property is a fundamental task in theoretical computer science, with practical applications in many branches of data mining and network analysis. It is often of interest to only consider solutions (subgraphs) that are maximal under inclusion, and to achieve output-sensitive complexity, i.e., bounding the running time with respect to the number of subgraphs produced. In this paper, we provide a survey of techniques for designing output-sensitive algorithms for subgraph enumeration, including partition-based approaches such as flashlight search, solution-graph traversal methods such as reverse search, and cost amortization strategies such as push-out amortization. We also briefly discuss classes of efficiency, hardness of enumeration, and variants such as approximate enumeration. The paper is meant as an accessible handbook for learning the basics of the field and as a practical reference for selecting state-of-the-art subgraph enumeration strategies fitting to one’s needs.
2025
OpenAccess Series in Informatics
From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 2025
ita
2025
Conte A.; Kurita K.; Marino A.; Punzi G.; Uno T.; Wasa K.
File in questo prodotto:
File Dimensione Formato  
OASIcs.Grossi.19.pdf

accesso aperto

Tipologia: Pdf editoriale (Version of record)
Licenza: Open Access
Dimensione 1.01 MB
Formato Adobe PDF
1.01 MB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1501749
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact