general.hpp File Reference

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

Go to the source code of this file.


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.

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".
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.
  • 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).
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.