Frobby 0.10.0
Loading...
Searching...
No Matches
SizeMaxIndepSetAlg Class Reference

#include <SizeMaxIndepSetAlg.h>

Public Member Functions

void run (Ideal &ideal)
mpz_class getMaxIndepSetSize ()

Detailed Description

Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.

Currently the only functionality is to compute the size of such a set. This amounts to finding the dimension of a monomial ideal, which can be done by taking the radical and then using this algorithm.

The algorithm is a branch-and-bound algorithm lifted from Macaulay 2, though the implementation here is much faster as of July 2009. I don't know why it is so much faster, since it is nearly equivalent to what Macalay 2 does.

The state of the algortihm is a partially-decided set of nodes of the hypergraph, where each node can be definitely in the set, definitely not in the set or undecided. In the beginning every variable is undecided.

The algorithm then scans through the edges. For each edge, it may be that it definitely does not make the current set dependent. If so, we skip past the edge. It may also definitely make the current set dependent. If so, we discard the current set. If it is undecided whether the edge makes the set dependent, we choose some undecided node that makes this happen, and recurse on the possibility where it is not in the set (and so makes the set not dependent according to this edge). When we are done, we then consider the case where the node is definitely in the set, restarting the case-distinctions above.

The bound used is simply the number of definitely excluded nodes. If this is more than or equal to the least number of excluded nodes seen so far, then there is no reason to consider such a set further, since it can lead to no improvement.

Note that in the base case, not every independent set considered is maximal according to inclusion, but since we only consider the size-maximal ones, the ones we care about are maximal with respect to inclusion.

Member Function Documentation

◆ getMaxIndepSetSize()

mpz_class SizeMaxIndepSetAlg::getMaxIndepSetSize ( )

Returns the largest size over all independent sets of the hypergraph passed to run.

Returns varCount + 1 if the hypergraph has no independent sets, which is to say that ideal is generated by the identity. The returned value is undefined if run has not been called first.

◆ run()

void SizeMaxIndepSetAlg::run ( Ideal & ideal)

Run the algorithm on ideal. Should work but has not been tested when called more than once on the same object. May rearrange the generators of ideal. ideal must be square free and minimally generated. Thus ideal is the edge ideal of some hypergraph, and it is this hypergraph that the algorithm runs on.


The documentation for this class was generated from the following files: