Polynomial delay algorithm for listing minimal edge dominating sets in graphs
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Abstract: The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size of all its minimal transversals, is a fifty years old open problem, and up to now there are few examples of hypergraph classes where the problem is solved. A minimal dominating set in a graph is a subset of its vertex set that has a non empty intersection with the closed neighborhood of every vertex. It is proved in [M. M. Kant'e, V. Limouzy, A. Mary, L. Nourine, On the Enumeration of Minimal Dominating Sets and Related Notions, In Revision 2014] that the enumeration of minimal dominating sets in graphs and the enumeration of minimal transversals in hypergraphs are two equivalent problems. Hoping this equivalence can help to get new insights in the Transversal problem, it is natural to look inside graph classes. It is proved independently and with different techniques in [Golovach et al. - ICALP 2013] and [Kant'e et al. - ISAAC 2012] that minimal edge dominating sets in graphs (i.e, minimal dominating sets in line graphs) can be enumerated in incremental output-polynomial time. We provide the first polynomial delay and polynomial space algorithm that lists all the minimal edge dominating sets in graphs, answering an open problem of [Golovach et al. - ICALP 2013]. Besides the result, we hope the used techniques that are a mix of a modification of the well-known Berge's algorithm and a strong use of the structure of line graphs, are of great interest and could be used to get new output-polynomial time algorithms.
Recommendations
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
- A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
- Enumeration of minimal dominating sets and variants
Cites work
- A new polynomial-time algorithm for linear programming
- Algorithm Theory - SWAT 2004
- An Efficient Algorithm for the Transversal Hypergraph Generation
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- Efficient algorithms for dualizing large-scale hypergraphs
- Enumerating minimal subset feedback vertex sets
- Enumeration of the monomials of a polynomial and related complexity classes
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Generating cut conjunctions in graphs and related problems
- scientific article; zbMATH DE number 43754 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- On enumerating all minimal solutions of feedback problems
- On the enumeration and counting of minimal dominating sets in interval and permutation graphs
- On the enumeration of minimal dominating sets and related notions
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- Reverse search for enumeration
- Rigorous and accurate enclosure of invariant manifolds on surfaces
Cited in
(26)- Enumeration of maximal irredundant sets for claw-free graphs
- Efficient enumeration of dominating sets for sparse graphs
- A polynomial delay algorithm for enumerating 2-edge-connected induced subgraphs
- On the complexity of solution extension of optimization problems
- Extension and its price for the connected vertex cover problem
- Enumeration and maximum number of minimal dominating sets for chordal graphs
- Invited talks
- Upper domination: complexity and approximation
- A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
- Counting minimal dominating sets
- Minimal dominating sets in interval graphs and trees
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- On kernelization for edge dominating set under structural parameters
- Efficient enumeration of dominating sets for sparse graphs
- Enumeration of maximal irredundant sets for claw-free graphs
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- scientific article; zbMATH DE number 7650296 (Why is no real title available?)
- Minimal Roman dominating functions: extensions and enumeration
- Minimal Roman dominating functions: extensions and enumeration
- An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraints
- Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
- Enumerating minimal defensive alliances
- Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
- Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond
- Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
- Enumerating minimal dominating sets and variants in chordal bipartite graphs
This page was built for publication: Polynomial delay algorithm for listing minimal edge dominating sets in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449842)
