OKlibrary  0.2.1.6
general.hpp File Reference

Plans for the module on hypergraph transversals. More...

Go to the source code of this file.

Namespaces

namespace  OKlib::Combinatorics::Hypergraphs::Transversals

Components for handling hypergraph transversals.

namespace  OKlib

All components of the OKlibrary.

namespace  OKlib::Combinatorics

The part of the OKlibrary for general combinatorics.

namespace  OKlib::Combinatorics::Hypergraphs

Supermodule for dedicated hypergraph algorithms.

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 3-uniform 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 hyperedge-complementation) 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
1. enumerating transversals
2. enumerating edge covers
3. enumerating independent sets
for hypergraphs can each be reduced to each other by a combination of dualisation and hyperedge-complementation.
• 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 SAT-generalisation
• 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.