Plans for the module on hypergraph transversals.
More...
Go to the source code of this file.
Detailed Description
Plans for the module on hypergraph transversals.
 Todo:
 Connections
 Todo:
 Organisation of the module

DONE (we have "Bounded" and "Minimal") Perhaps we should have submodules "Bounded", "Minimum".

Another submodule could be "Exact", which could again have submodules "Bounded" and "Minimal".
 Todo:
 Literature exploration

What is known meanwhile about the existence of polynomial delay enumeration of Tr(G) for hypergraphs G?

For example Wahlstroem has an algorithm for enumerating Tr(G) for 3uniform G  worth implementing? Likely one needs to extract a heuristical generalisation.

The dual problem to hypergraph transversal enumeration (using the dual hypergraph) is enumeration of all edge covers of a hypergraph (see Hypergraphs/HyperedgeCoverings/plans/general.hpp)  has this formulation advantages / disadvantages?

The complementary problem (by hyperedgecomplementation) to hypergraph transversal enumeration is enumeration of all independent sets (see Hypergraphs/IndependentSets/plans/general.hpp)  again, has this formulation advantages / disadvantages?

The graph case:

Transversals for graphs are called "vertex covers" (see Graphs/VertexCovers/plans/general.hpp); are there special algorithms?

Also the independent sets in graph deserve attention.

For graphs, finding a minimum edge cover can be done in polynomial time by means of maximum matching; worth investigating? Dualisation yields, that minimum transversals can be computed for hypergraphs with vertex degrees at most 2.
 Todo:
 Duality

So the three problems

enumerating transversals

enumerating edge covers

enumerating independent sets
for hypergraphs can each be reduced to each other by a combination of dualisation and hyperedgecomplementation.

We should develop hypergraph adapters, which do not need to actually perform the transformation, but provide a "view".

Perhaps this should be supported by the hypergraph concepts (otherwise we have to handle expression templates).
 Todo:
 Compare with the SATgeneralisation

All the algorithms in this module can be naturally generalised to (generalised) SAT; see AllSolutions/plans/MinimalAssignments.hpp.

So shall we only implement the general SAT case?

The embedding G > F is given here by using the vertices v as variables with domains D_v = {0}, and where all literals are positive monosigned, i.e., "v=0".

An alternative is to use boolean variables: Then we have also the possibility to cross out vertices (by setting the corresponding literals to false).
Definition in file general.hpp.