Proximity Search for Maximal Subgraph Enumeration
From MaRDI portal
Publication:5048293
DOI10.1137/20M1375048zbMATH Open1503.05061arXiv1912.13446OpenAlexW2997095431MaRDI QIDQ5048293FDOQ5048293
Authors: Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, Luca Versari 
Publication date: 15 November 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Abstract: This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of Maximal Bipartite Subgraphs, Maximal k-Degenerate Subgraphs (for bounded k), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or "supergraph", and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential: we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met.
Full work available at URL: https://arxiv.org/abs/1912.13446
Recommendations
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
- The approximation of maximum subgraph problems
- Proportionally dense subgraph of maximum size: complexity and approximation
- scientific article; zbMATH DE number 1830717
- Maximal clique enumeration in finding near neighbourhoods
- In search of the densest subgraph
- Finding optimal subgraphs by local search
- Finding maximal common subgraphs via time-space efficient reverse search
- On the complexity of the maximum subgraph problem
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)
Cites Work
- The vectorization of ITPACK 2C
- Title not available (Why is that?)
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Incidence matrices and interval graphs
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Efficiency of a Good But Not Linear Set Union Algorithm
- A New Algorithm for Generating All the Maximal Independent Sets
- Title not available (Why is that?)
- k-Degenerate Graphs
- On cliques in graphs
- Reverse search for enumeration
- Combinatorial bounds via measure and conquer
- On the Enumeration of Minimal Dominating Sets and Related Notions
- Algorithmic Aspects of Vertex Elimination on Graphs
- On generating all maximal independent sets
- Largest chordal and interval subgraphs faster than \(2^n\)
- Title not available (Why is that?)
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- On enumerating all minimal solutions of feedback problems
- Enumeration aspects of maximal cliques and bicliques
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- Compression via Matroids
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Title not available (Why is that?)
- Efficiently enumerating minimal triangulations
- Title not available (Why is that?)
- Efficient enumeration of bipartite subgraphs in graphs
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
Cited In (3)
This page was built for publication: Proximity Search for Maximal Subgraph Enumeration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048293)
