general.hpp File Reference

Plans for the module on computing hypergraph transversals of size at most k. More...

Go to the source code of this file.


namespace  OKlib::Combinatorics::Hypergraphs::Transversals::Bounded

Components for handling hypergraph transversals of bounded size.

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.

namespace  OKlib::Combinatorics::Hypergraphs::Transversals

Components for handling hypergraph transversals.

Detailed Description

Plans for the module on computing hypergraph transversals of size at most k.

Connections to other modules
Trivial algorithm for input G, k
  • The task is to find a transversal T with |T| <= k.
  • Outline of the algorithm:
    1. Another input is a vertex set T of size <= k, to be extended to a transversal of size at most k.
    2. If all hyperedges are covered, return T.
    3. Otherwise, if |T| is of size = k, then return "impossible".
    4. Otherwise choose some hyperedge H which is not hit by T, and for all v in H try recursively T + {v}.
  • If a minimal transversal T is needed (w.r.t. set-inclusion), then by some heuristics unnecessary vertices in T are removed (iteratively).
  • For the choice of H the simplest heuristics is to choose a smallest H.
    1. Simplest to order the hyperedges once at the beginning.
    2. Stronger if the hypergraph datastructure gives access to the current smallest hyperedge; but this is not enough, we need the smallest *uncovered* hyperedge (one whose size has not changed since the beginning).
  • For the order of vertices, the simplest heuristics is to order them in descending degree.
  • Special services needed from the hypergraph:
    1. Necessary is a largest hyperedge.
    2. For heuristical purposes a smallest hyperedge (strongest: amongst the untouched hyperedges).
    3. For heuristical purposes a vertex of largest degree.
An "eager, binary" variation of the (above) trivial algorithm
  • The algorithms transversals_be, transversals_bes in ComputerAlgebra/Hypergraphs/Lisp/Transversals/Bounded/MaintainingBound.mac implement the above algorithm, but with the following two differences:
    1. Above we use "clause branching", while these algorithms use binary branching; this should be better.
    2. Above the handling of the hypergraph is "lazy" (not performing the assignment), while these algorithms are "eager" (actually performing the assignment).
  • DONE (implemented transversals_bvs, but without any further embellishments) We should directly implement the algorithms transversals_be, transversals_bes in C++:
    1. As a first prototype for the concept of hypergraphs as (just) containers of hyperedges; here perhaps using std::vector for the list, and std::set for the hyperedges.
    2. A simple generic strategy provides the possibility to use different heuristics for the choice of the branching vertex.
    3. For vertices we just have integers in mind (but this is not hardcoded).
  • This would extend the already existing "non-abstract" hypergraph concepts; programming at this level quite similar to the Maxima/Lisp level.
  • Compare also the point below about enumerating all transversals.
Enumerating all transversals T with |T| <= k
  • The above trivial algorithm also enumerates all transversals T with |T| <= k, when just continuing the process until the end.
    1. However, to really obtain all such transversals, one needs to use the set of formal vertices, not just those left over.
    2. One should construct a little example.
    3. Of course, we are not interesting in computing all transversals (from the minimal transversals we trivially could obtain them by padding), but the point is that considering only the existing vertices already achieves some simple form of "tree pruning".
    4. See the specification of transversals_be in ComputerAlgebra/Hypergraphs/Lisp/Transversals/Bounded/MaintainingBound.mac.
  • However now we really only want to find minimal transversals (w.r.t. inclusion).
    1. This can be achieved by computing all and then applying subsumption elimination, but we need also more efficient solutions.
    2. It seems natural, as above for a transversal T found just to minimise it (trivially), and then to prune parts of the tree which cannot contribute a minimal transversal anymore. This process is similar to tree pruning ("intelligent backtracking") for SAT.
    3. Of course, if k is at most the transversal number, then no further steps are needed; this situation arises naturally when either searching for a minimum transversal from below, or when computing transversal numbers for monotonically increasing sequences of hypergraphs (at one new vertex at each step); see Experimentation/Investigations/RamseyTheory/VanderWaerdenProblems/Transversals/plans/general.hpp.
    4. Perhaps actually such pruning cannot be done efficiently? It should be the case that when branching on a still occurring vertex, then the subtree contains at least one minimal transversal (if not already some superfluous vertex has been included)?
Application BoundedTransversals_bv
  • Perhaps we should provide some variations.
    1. Instead of using sets sorted by size one could just use sets (this should be slower).
    2. Instead of using std::set, one could use std::vector, and sort it when needed.
  • The various set-operation used in Transversals::Bounded_transversals_bv should be provided independently, so that the code becomes clearer.
  • And G_with_a could be a vector.
As generalised-SAT algorithms
  • The above algorithms can be viewed as very simple backtracking generalised-SAT solvers, where the condition on the number of 1-settings in the partial assignment is integrated into the backtracking mechanism.
Overview on more sophisticated algorithms

Definition in file general.hpp.