Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes

DOI10.1016/J.DAM.2023.10.025MaRDI QIDQ6145807zbMATH OpenOpenAlexFDO

Authors Caroline Brosse, A. Lagoutte, Vincent Limouzy, Arnaud Mary, Lucas Pastor

Publication date 9 January 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.01031

zbMATH Keywords

algorithmic enumerationsalgorithmsgraph classesproximity search

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper, we are interested in algorithms that take in input an arbitrary graph $G$, and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of $G$ which fulfil a given property $Pi$. All over this paper, we study several different properties $Pi$, and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, sub-cographs and some subclasses of cographs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal independent sets of an auxiliary graph. For cographs and some subclasses , the algorithms rely on a framework recently introduced by Conte & Uno called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property $Pi$ that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every "interesting" hereditary property $Pi$. We extend the hardness result to some specific edge version of the extension problem.

Recommendations

• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• Proximity Search for Maximal Subgraph Enumeration
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Enumeration of minimal dominating sets and variants

Cites work

• A Linear Recognition Algorithm for Cographs
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithmic graph theory and perfect graphs
• Analysis and enumeration. Algorithms for biological graphs
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Characterizing and computing minimal cograph completions
• Complement reducible graphs
• Edge-Deletion Problems
• Efficient enumeration of bipartite subgraphs in graphs
• Enumeration of maximal common subsequences between two strings
• Finding All Spanning Trees of Directed and Undirected Graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Graph Sandwich Problems
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1104328 (Why is no real title available?)
• scientific article; zbMATH DE number 2081005 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Minimal split completions
• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• On cliques in graphs
• On generating all maximal independent sets
• On maximal chain subgraphs and covers of bipartite graphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of solution extension of optimization problems
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• On the enumeration of minimal dominating sets and related notions
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Reverse search for enumeration
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(2)

• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Listing maximal H-free subgraphs

This page was built for publication: Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145807)