Metadata about: Our main objective is the COMPRESSED enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author's best knowledge the only previous attempt towards compression, due to Toda [T], is based on BDD's and much different from our techniques. Preliminary numerical experiments show that traditional one-by-one enumeration schemes cannot compete against compressed enumeration when the degree of compression is high. Despite the fact that thorough numerical experiments are postponed to a later version of our article, several tools to enhance compression (inclusion-exclusion, a matroid theorem of Rado, or adding dual kinds of wildcards) are put in place and their pros and cons are evaluated. Nevertheless, classic one-by-one enumeration is not neglected. Corollary 2 states that under mild provisos all perfect matchings of a graph can be enumerated in polynomial total time. Likewise all minimal edge-covers of a graph (Corollary 6). Furthermore, enumerating all minimal hypergraph transversals is fixed-parameter tractable for novel types of parameters (Corollary 5 and 4.6.3). Exact hitting sets constitute only a 'side show' but we start with them by pedagogical reasons: Our wildcard method is more clear-cut for exact hitting sets than for minimal hitting sets.

About: Our main objective is the COMPRESSED enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author's best knowledge the only previous attempt towards compression, due to Toda [T], is based on BDD's and much different from our techniques. Preliminary numerical experiments show that traditional one-by-one enumeration schemes cannot compete against compressed enumeration when the degree of compression is high. Despite the fact that thorough numerical experiments are postponed to a later version of our article, several tools to enhance compression (inclusion-exclusion, a matroid theorem of Rado, or adding dual kinds of wildcards) are put in place and their pros and cons are evaluated. Nevertheless, classic one-by-one enumeration is not neglected. Corollary 2 states that under mild provisos all perfect matchings of a graph can be enumerated in polynomial total time. Likewise all minimal edge-covers of a graph (Corollary 6). Furthermore, enumerating all minimal hypergraph transversals is fixed-parameter tractable for novel types of parameters (Corollary 5 and 4.6.3). Exact hitting sets constitute only a 'side show' but we start with them by pedagogical reasons: Our wildcard method is more clear-cut for exact hitting sets than for minimal hitting sets.

an Entity references as follows:

Graph IRI	Count
http://ns.inria.fr/covid19/graph/entityfishing	10
http://ns.inria.fr/covid19/graph/articles	3

Faceted Search & Find service v1.13.91

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Copyright © 2009-2025 OpenLink Software