Proximity Search for Maximal Subgraph Enumeration

DOI10.1137/20M1375048zbMATH Open1503.05061OpenAlexW2997095431MaRDI 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

zbMATH Keywords

proximity searchpolynomial delaygraph enumerationoutput polynomial

Mathematics Subject Classification ID

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
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• 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
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• Efficient enumeration of bipartite subgraphs in graphs
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• New polynomial delay bounds for maximal subgraph enumeration by proximity search

Cited In (7)

• Maximum dissociation sets in subcubic trees
• Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
• Towards Finding Maximal Subrelations with Desired Properties
• Enumerating connected induced subgraphs: improved delay and experimental comparison
• Traversing combinatorial 0/1-polytopes via optimization
• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• Efficient enumeration of bipartite subgraphs in graphs

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)