Proximity Search for Maximal Subgraph Enumeration
From MaRDI portal
Publication:5048293
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.
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
Cites work
- scientific article; zbMATH DE number 3679885 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 1796975 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- k-Degenerate Graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Algorithmic Aspects of Vertex Elimination on Graphs
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Combinatorial bounds via measure and conquer
- Compression via Matroids
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficient enumeration of bipartite subgraphs in graphs
- Efficiently enumerating minimal triangulations
- Enumeration aspects of maximal cliques and bicliques
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Graph-Theoretic Concepts in Computer Science
- Incidence matrices and interval graphs
- Largest chordal and interval subgraphs faster than \(2^n\)
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Listing all maximal cliques in large sparse real-world graphs
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
- On cliques in graphs
- On enumerating all minimal solutions of feedback problems
- On generating all maximal independent sets
- On the enumeration of minimal dominating sets and related notions
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- Reverse search for enumeration
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- The vectorization of ITPACK 2C
- The worst-case time complexity for generating all maximal cliques and computational experiments
Cited in
(7)- Towards Finding Maximal Subrelations with Desired Properties
- Maximum dissociation sets in subcubic trees
- Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
- Traversing combinatorial 0/1-polytopes via optimization
- Efficient enumeration of bipartite subgraphs in graphs
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
- Enumerating connected induced subgraphs: improved delay and experimental comparison
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)
