general.hpp File Reference

Plans regarding hypergraphs transversals (in Maxima/Lisp) More...

Go to the source code of this file.

Detailed Description

Plans regarding hypergraphs transversals (in Maxima/Lisp)

  • Split Transversals/Transversals.mac into several files.
  • Perhaps Transversals/Basics.mac, Transversals/Minimal.mac, Transversals/Bounded.mac, and Transversals/Greedy.mac.
The triangle of the three possibilities
  • The complementary problem is about maximal independent sets, the dual problem is about hyperedge coverings.
  • Likely these problems have each at least one natural algorithm, different from the translations of the others.
  • So we need to provide a general scheme for translations.
  • See Combinatorics/Hypergraphs/IndependentSets/plans/general.hpp.
  • The test-function okltest_ind_hg should be a generic test-function, applicable to any function for computing the hypergraph of (maximal) independent subsets (the "independence hypergraph").
  • So, as with transversals, we must distinguish between the (many) possible algorithms for ind_hg.
  • An alternative method for computing ind_hg is by direct construction:
    1. Bottom-up: Start with all independent subsets of size 0. Then for k=0, 1, ... take the sets of size k and consider all possibilities to a vertex, obtain so level k+1. Those which cannot be extended go to the final result, while otherwise the processed level is removed.
    2. This algorithm is for example efficient for complete graphs.
    3. Top-down: We start with the full vertex-set at level n. Then for k = n,n-1, ... all subsets which are independent are moved to the final result, while otherwise all possible (k-1)-subsets are formed, which makes level k-1, and level k is removed.
    4. This algorithm is efficient for hypergraphs with no hyperedges.
  • Of course, a question is whether independence hypergraphs are really on its own, or we should standardise all considerations by considering transversals? Just taking the edgewise-complement is not a big step? But it's a step, and also the literature is different.

Definition in file general.hpp.