Hypergraphs Invariants API

Hypergraph Invariants

graphcalc.hypergraphs.invariants.acyclicity.berge_girth(H: Hypergraph) → int | None[source]

Return the Berge girth of a hypergraph.

The Berge girth is the minimum number of hyperedges in a Berge cycle of the hypergraph. If the hypergraph has no Berge cycle, this function returns None.

This implementation computes the girth through the incidence graph of the hypergraph. The incidence graph is the bipartite graph with one part corresponding to vertices, the other part corresponding to hyperedges, and an incidence edge joining \(v\) to \(e\) whenever \(v \in e\).

A Berge cycle of length \(k\) corresponds to a cycle of length \(2k\) in the incidence graph. Therefore this function computes the length of the shortest cycle in the incidence graph and divides by two.

Parameters:: H (HypergraphLike) – A finite hypergraph.
Returns:: The length of the shortest Berge cycle, measured in number of hyperedges, or None if the hypergraph is Berge-acyclic.
Return type:: int or None

Notes

If the incidence graph is acyclic, then the hypergraph is Berge-acyclic.
The smallest possible cycle in a bipartite graph has length 4, so the smallest possible Berge cycle has length 2 under this convention.

Examples

>>> import graphcalc.hypergraphs as hc
>>> from graphcalc.hypergraphs.invariants.acyclicity import berge_girth
>>> H = hc.Hypergraph(E=[{1, 2}, {2, 3}, {1, 3}])
>>> berge_girth(H)
3

graphcalc.hypergraphs.invariants.acyclicity.is_alpha_acyclic(H: Hypergraph) → bool[source]

Return whether a hypergraph is alpha-acyclic.

A hypergraph is alpha-acyclic if it can be reduced to the empty hypergraph by repeated application of the GYO reduction rules:

remove any vertex that belongs to at most one hyperedge, deleting it from that hyperedge, and
remove any hyperedge that is contained in another hyperedge.

This notion is one of the standard acyclicity concepts for hypergraphs and database schemas.

Parameters:: H (HypergraphLike) – A finite hypergraph.
Returns:: True if the GYO reduction eliminates all nonempty hyperedges. Otherwise False.
Return type:: bool

Notes

Empty hyperedges are ignored by this implementation when initializing the reduction process. This is consistent with viewing them as carrying no vertex-incidence structure for the GYO procedure.

The algorithm works on mutable copies of the hyperedges and does not modify H.

Examples

>>> import graphcalc.hypergraphs as hc
>>> from graphcalc.hypergraphs.invariants.acyclicity import is_alpha_acyclic
>>> H = hc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> is_alpha_acyclic(H)
True

graphcalc.hypergraphs.invariants.acyclicity.is_berge_acyclic(H: Hypergraph) → bool[source]

Return whether a hypergraph is Berge-acyclic.

A hypergraph is Berge-acyclic if it contains no Berge cycle. Equivalently, its incidence graph is acyclic.

Parameters:: H (HypergraphLike) – A finite hypergraph.
Returns:: True if H has no Berge cycle. Otherwise False.
Return type:: bool

Definitions

Let H = (V, E) be a finite hypergraph.

The 2-section (or primal graph) of H is the graph on vertex set V in which two distinct vertices u and v are adjacent whenever there exists a hyperedge e in E such that {u, v} subseteq e.

A set D subseteq V is a dominating set of H if every vertex v in V \ D has a neighbor in D in the 2-section. Equivalently,

for every v in V,
v in D or there exists u in D such that u and v lie together in some hyperedge.

A set D subseteq V is a total dominating set of H if every vertex v in V has a distinct neighbor in D in the 2-section. Equivalently,

for every v in V,
there exists u in D, u != v, such that u and v lie together in some hyperedge.

Thus total domination does not allow self-domination and is infeasible whenever the 2-section contains an isolated vertex.

Functions

minimum_dominating_set: Compute a minimum dominating set of a hypergraph.
domination_number: Compute the domination number gamma(H).
minimum_total_dominating_set: Compute a minimum total dominating set of a hypergraph.
total_domination_number: Compute the total domination number gamma_t(H).

Notes

These routines formulate domination and total domination as 0-1 linear programs and solve them using the shared GraphCalc solver framework via graphcalc.solvers.with_solver.

On 2-uniform hypergraphs (ordinary simple graphs), these notions reduce exactly to the usual graph domination and total domination problems.

graphcalc.hypergraphs.invariants.domination.domination_number(H: Hypergraph, **solver_kwargs) → int[source]

Return the domination number of a hypergraph.

The domination number of a hypergraph, under the 2-section definition, is

\[\gamma(H) = \min\{ |D| : D \subseteq V(H),\ D \text{ dominates } H \}.\]

Parameters:

H (HypergraphLike) – A finite hypergraph.
k (int, optional) – Passed through to minimum_dominating_set().
verbose (bool, default=False) – Passed through to minimum_dominating_set().
solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Passed through to minimum_dominating_set().
solver_options (dict, optional) – Passed through to minimum_dominating_set().

Returns:

The domination number \(\gamma(H)\).

Return type:

int

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.domination import domination_number
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> domination_number(H)
1

graphcalc.hypergraphs.invariants.domination.minimum_dominating_set(H: Hypergraph, *, k: int | None = None, verbose: bool = False, solve=None) → Set[Hashable][source]

Return a minimum dominating set of a hypergraph.

This function uses domination in the 2-section graph of the hypergraph. A set D subseteq V(H) is a dominating set if every vertex either belongs to D or has a neighbor in D in the 2-section. Equivalently,

\[\forall v \in V(H), \quad v \in D \;\; \text{or} \;\; \exists u \in D \text{ such that } \{u,v\} \subseteq e \text{ for some } e \in E(H).\]

The optimization problem solved is:

\[\min \sum_{v \in V(H)} x_v\]

subject to

\[x_v + \sum_{u \in N_H(v)} x_u \ge 1 \quad \text{for all } v \in V(H),\]

where N_H(v) denotes the open neighborhood of v in the 2-section graph and each x_v is binary.

Parameters:

H (HypergraphLike) – A finite hypergraph.
k (int, optional) – If provided, first verify that H is k-uniform. This is only a validation check and is not required for correctness.
verbose (bool, default=False) – If True, print solver status, objective value, and extracted solution.
solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver specification handled by graphcalc.solvers.resolve_solver().
solver_options (dict, optional) – Extra keyword arguments used when constructing the solver.

Returns:

A minimum dominating set of H.

Return type:

set of hashable

Raises:

ValueError – If k is provided and H is not k-uniform.
ValueError – If no optimal solution is found by the solver.

Notes

Vertices isolated in the 2-section must belong to every dominating set. This includes vertices that are not contained in any hyperedge, as well as vertices that appear only in singleton or empty-incidence contexts.

If H has no vertices, the empty set is returned.

Examples

>>> import graphcalc.hypergraphs as hc
>>> from graphcalc.hypergraphs.invariants.domination import minimum_dominating_set
>>> H = hc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> D = minimum_dominating_set(H)
>>> D == {2}
True

>>> from graphcalc.hypergraphs.invariants.domination import domination_number
>>> domination_number(H)
1

graphcalc.hypergraphs.invariants.domination.minimum_total_dominating_set(H: Hypergraph, *, k: int | None = None, verbose: bool = False, solve=None) → Set[Hashable][source]

Return a minimum total dominating set of a hypergraph.

This function uses total domination in the 2-section graph of the hypergraph. A set D subseteq V(H) is a total dominating set if every vertex has a distinct neighbor in D in the 2-section. Equivalently,

\[\forall v \in V(H), \quad \exists u \in D,\; u \ne v, \text{ such that } \{u,v\} \subseteq e \text{ for some } e \in E(H).\]

Thus self-domination is not allowed.

The optimization problem solved is:

\[\min \sum_{v \in V(H)} x_v\]

subject to

\[\sum_{u \in N_H(v)} x_u \ge 1 \quad \text{for all } v \in V(H),\]

where N_H(v) denotes the open neighborhood of v in the 2-section graph and each x_v is binary.

Parameters:

H (HypergraphLike) – A finite hypergraph.
k (int, optional) – If provided, first verify that H is k-uniform. This is only a validation check and is not required for correctness.
verbose (bool, default=False) – If True, print solver status, objective value, and extracted solution.
solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver specification handled by graphcalc.solvers.resolve_solver().
solver_options (dict, optional) – Extra keyword arguments used when constructing the solver.

Returns:

A minimum total dominating set of H.

Return type:

set of hashable

Raises:

ValueError – If k is provided and H is not k-uniform.
ValueError – If the 2-section contains an isolated vertex, in which case no total dominating set exists.
ValueError – If no optimal solution is found by the solver.

Notes

If H has no vertices, the empty set is returned.

Hypergraphs with isolated vertices in the 2-section have no total dominating set, since such vertices have no distinct neighbor available to dominate them.

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.domination import minimum_total_dominating_set
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> T = minimum_total_dominating_set(H)
>>> len(T)
2

graphcalc.hypergraphs.invariants.domination.total_domination_number(H: Hypergraph, **solver_kwargs) → int[source]

Return the total domination number of a hypergraph.

The total domination number of a hypergraph, under the 2-section definition, is

\[\gamma_t(H) = \min\{ |D| : D \subseteq V(H),\ D \text{ totally dominates } H \}.\]

Parameters:

H (HypergraphLike) – A finite hypergraph.
k (int, optional) – Passed through to minimum_total_dominating_set().
verbose (bool, default=False) – Passed through to minimum_total_dominating_set().
solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Passed through to minimum_total_dominating_set().
solver_options (dict, optional) – Passed through to minimum_total_dominating_set().

Returns:

The total domination number \(\gamma_t(H)\).

Return type:

int

Raises:

ValueError – If no total dominating set exists.

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.domination import total_domination_number
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> total_domination_number(H)
2

graphcalc.hypergraphs.invariants.dsi.degree_sequence(H: Hypergraph, *, nonincreasing: bool = True) → list[int][source]

Return the vertex degree sequence of a hypergraph.

The degree sequence of a hypergraph is the list of vertex degrees, optionally sorted in nonincreasing or nondecreasing order.

Parameters:

H (HypergraphLike) – A finite hypergraph.
nonincreasing (bool, default=True) – If True, return the sequence sorted from largest to smallest. If False, return the sequence sorted from smallest to largest.

Returns:

The sorted degree sequence of H.

Return type:

list of int

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.dsi import degree_sequence
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}, {2, 3, 4}])
>>> degree_sequence(H)
[3, 2, 1, 1]
>>> degree_sequence(H, nonincreasing=False)
[1, 1, 2, 3]

graphcalc.hypergraphs.invariants.dsi.generalized_annihilation_number(H: Hypergraph, k: int | None = None) → int[source]

Return the scaled annihilation number of a k-uniform hypergraph.

Let \(H\) be a k-uniform hypergraph with m = |E(H)| and let

\[d_1 \le d_2 \le \cdots \le d_n\]

be the nondecreasing vertex degree sequence.

The scaled annihilation number is defined by

\[a_k(H) = \max \left\{ t : \sum_{i=1}^{t} d_i \le (k-1)m \right\}.\]

For k=2, this reduces to the classical annihilation number of a graph, since (k-1)m = m.

Parameters:

H (HypergraphLike) – A finite hypergraph.
k (int or None, default=None) – Target uniformity. If None, infer from the hyperedges of H.

Returns:

The scaled annihilation number \(a_k(H)\).

Return type:

int

Raises:

ValueError – If H is not k-uniform.
ValueError – If k is None and H has no hyperedges.

Notes

If H has no hyperedges, the function returns |V(H)|.

For a k-uniform hypergraph, this parameter depends only on the degree multiset, since

\[\sum_{v \in V(H)} d(v) = k|E(H)|.\]

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.dsi import generalized_annihilation_number
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> generalized_annihilation_number(H, k=2)
2

graphcalc.hypergraphs.invariants.dsi.generalized_havel_hakimi_residue(H: Hypergraph, *, k: int | None = None, trace: bool = False) → int[source]

Return a Havel–Hakimi-type residue for a k-uniform hypergraph.

This function defines a degree-sequence invariant for uniform hypergraphs that extends the classical Havel–Hakimi residue of graphs.

Let \(H=(V,E)\) be a finite k-uniform hypergraph, and let \(d(v)\) denote the degree of vertex \(v\). Write the multiset of vertex degrees as the degree sequence of H.

Case k = 2

The function returns the classical Havel–Hakimi residue of the graph degree sequence.

Case k >= 3

The function applies the following fixed greedy reduction rule to the degree multiset:

Repeat while the current maximum degree is positive:

Remove one occurrence of the current maximum degree \(s\).
Perform \(s\) micro-steps. In each micro-step: select the k-1 currently largest remaining degrees and subtract 1 from each of them.

If at any micro-step fewer than k-1 positive degrees remain, the process is declared to fail and the function returns 0.

When the process terminates successfully, all remaining entries are zero, and the residue is defined to be the number of remaining entries.

Parameters:

H (HypergraphLike) – A finite hypergraph.
k (int or None, default=None) – Target uniformity. If None, infer from the hyperedges of H.
trace (bool, default=False) – If True, print intermediate sequences for the classical k=2 case. For k>=3, no intermediate trace is printed.

Returns:

The residue value defined by the above reduction process.

Return type:

int

Raises:

ValueError – If H is not k-uniform.
ValueError – If k is None and H has no hyperedges.

Notes

If H has no hyperedges, the function returns |V(H)|.
For k=2, this exactly recovers the classical graph residue.
For k>=3, this defines a consistent degree-sequence invariant via a fixed greedy rule, but no universal extremal interpretation is assumed unless separately proved.

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.dsi import generalized_havel_hakimi_residue
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> generalized_havel_hakimi_residue(H, k=2)
2

graphcalc.hypergraphs.invariants.dsi.hh_residue_graph_degree_sequence(deg_seq: list[int] | tuple[int, ...], *, trace: bool = False) → int[source]

Return the classical Havel–Hakimi residue of a degree sequence.

Let \(d = (d_1, \dots, d_n)\) be a finite sequence of nonnegative integers. The Havel–Hakimi reduction repeatedly transforms the sequence as follows:

Sort the current sequence in nonincreasing order.
If the first entry is 0, stop.
Remove the first entry \(s\).
Subtract 1 from each of the next \(s\) entries.

If at any step \(s\) exceeds the number of remaining entries, or a negative entry is produced, then the sequence is not graphical and the process is invalid.

The residue is the number of entries remaining when the process stops, at which point all entries are zero.

For a simple graph \(G\), the residue \(R(G)\) is defined as the residue of its degree sequence.

Parameters:

deg_seq (list[int] or tuple[int, ...]) – A finite sequence of integer degrees.
trace (bool, default=False) – If True, print the intermediate sequences after each reduction step.

Returns:

The Havel–Hakimi residue of deg_seq.

Return type:

int

Raises:

ValueError – If a negative entry occurs in the input sequence.
ValueError – If the sequence is not graphical under the Havel–Hakimi process.

Notes

This routine is purely sequence-based and does not require an explicit graph realization.

graphcalc.hypergraphs.invariants.dsi.reverse_degree_sequence(H: Hypergraph) → list[int][source]

Return the nondecreasing degree sequence of a hypergraph.

This is a convenience wrapper for degree_sequence(H, nonincreasing=False).

Parameters:: H (HypergraphLike) – A finite hypergraph.
Returns:: The degree sequence sorted from smallest to largest.
Return type:: list of int

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.dsi import reverse_degree_sequence
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}, {2, 3, 4}])
>>> reverse_degree_sequence(H)
[1, 1, 2, 3]

graphcalc.hypergraphs.invariants.independence.independence_number(H: Hypergraph, **solver_kwargs) → int[source]: Return the independence number of a hypergraph.

graphcalc.hypergraphs.invariants.independence.maximum_independent_set(H: Hypergraph, *, verbose: bool = False, solve=None) → Set[Hashable][source]: Return a largest independent set of vertices in a hypergraph.

graphcalc.hypergraphs.invariants.matching.edge_cover_number(H: Hypergraph, **solver_kwargs) → int[source]: Return the edge cover number of a hypergraph.

graphcalc.hypergraphs.invariants.matching.fractional_matching_number(H: Hypergraph, *, verbose: bool = False, solve=None) → float[source]: Return the fractional matching number of a hypergraph.

graphcalc.hypergraphs.invariants.matching.matching_number(H: Hypergraph, **solver_kwargs) → int[source]: Return the matching number of a hypergraph.

graphcalc.hypergraphs.invariants.matching.maximum_matching(H: Hypergraph, *, verbose: bool = False, solve=None) → Set[FrozenSet[Hashable]][source]: Return a largest matching of hyperedges in a hypergraph.

graphcalc.hypergraphs.invariants.matching.minimum_edge_cover(H: Hypergraph, *, verbose: bool = False, solve=None) → Set[FrozenSet[Hashable]][source]: Return a minimum edge cover of a hypergraph.

graphcalc.hypergraphs.invariants.partite.is_r_partite_r_uniform(H: Hypergraph, r: int, *, exact_vertex_limit: int = 22) → Tuple[bool, Dict[Hashable, int] | None][source]

Determine whether a hypergraph is r-partite and r-uniform.

A hypergraph is r-uniform if every hyperedge has size exactly r.

A hypergraph is r-partite if its vertex set can be partitioned into r parts such that every hyperedge contains at most one vertex from each part. For an r-uniform hypergraph, this is equivalent to saying that every hyperedge contains exactly one vertex from each part.

This function checks both properties simultaneously and, if successful, returns a witness partition encoded as a map vertex -> part_index with values in {0, 1, ..., r-1}.

Parameters:

H (HypergraphLike) – A finite hypergraph.
r (int) – Target uniformity and number of parts.
exact_vertex_limit (int, default=22) – Maximum number of vertices allowed for the exact backtracking search.

Returns:

A pair (is_partite, witness) where is_partite is True if and only if H is r-partite and r-uniform. If True, witness is a partition map vertex -> part. Otherwise witness is None.

Return type:

tuple[bool, dict[Vertex, int] | None]

Raises:

ValueError – If r <= 0.
ValueError – If the number of vertices exceeds exact_vertex_limit.

Notes

The recognition is done by exact backtracking on vertex labels. It is intended for small hypergraphs.

The search orders vertices by decreasing degree to improve pruning.

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.partite import is_r_partite_r_uniform
>>> H = gc.Hypergraph(E=[{1, 3}, {2, 4}])
>>> is_r_partite_r_uniform(H, 2)
(True, {1: 0, 2: 0, 3: 1, 4: 1})

graphcalc.hypergraphs.invariants.structure.is_clutter(H: Hypergraph) → bool[source]

Return whether a hypergraph is a clutter.

A hypergraph is a clutter if no hyperedge properly contains another. Equivalently, the hyperedge family is an antichain under set inclusion.

In many texts, this is the same notion as a Sperner hypergraph.

Parameters:: H (HypergraphLike) – A finite hypergraph.
Returns:: True if for all distinct hyperedges \(e,f \in E(H)\), neither \(e \subset f\) nor \(f \subset e\) holds. Otherwise False.
Return type:: bool

Notes

Since the core hypergraph representation is simple, duplicate hyperedges are already excluded. Thus only proper containment needs to be checked.

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.structure import is_clutter
>>> H = gc.Hypergraph(E=[{1, 2}, {2, 3}])
>>> is_clutter(H)
True

>>> H = gc.Hypergraph(allow_singletons=True, E=[{1}, {1, 2}])
>>> is_clutter(H)
False

graphcalc.hypergraphs.invariants.structure.is_intersecting(H: Hypergraph) → bool[source]: Return whether a hypergraph is intersecting.

graphcalc.hypergraphs.invariants.structure.is_linear(H: Hypergraph) → bool[source]: Return whether a hypergraph is linear.

graphcalc.hypergraphs.invariants.structure.is_pair_covering(H: Hypergraph) → bool[source]: Return whether every pair of distinct vertices is contained in some hyperedge.

graphcalc.hypergraphs.invariants.structure.is_simple(H: Hypergraph) → bool[source]: Return whether a hypergraph is simple.

graphcalc.hypergraphs.invariants.structure.is_sperner(H: Hypergraph) → bool[source]: Return whether a hypergraph is Sperner.

graphcalc.hypergraphs.invariants.structure.is_t_intersecting(H: Hypergraph, t: int = 1) → bool[source]

Return whether a hypergraph is t-intersecting.

A hypergraph is t-intersecting if every two distinct hyperedges intersect in at least t vertices. That is,

\[|e \cap f| \ge t \quad \text{for all distinct } e,f \in E(H).\]

Parameters:

H (HypergraphLike) – A finite hypergraph.
t (int, default=1) – Required minimum intersection size.

Returns:

True if every pair of distinct hyperedges intersects in at least t vertices. Otherwise False.

Return type:

bool

Raises:

ValueError – If t < 0.

Notes

t = 1 recovers the usual notion of an intersecting hypergraph.
If t = 0, every hypergraph is vacuously t-intersecting.
Hypergraphs with at most one hyperedge are vacuously t-intersecting for every t >= 0.

Examples

>>> import graphcalc.hypergraphs as gc
>>> from graphcalc.hypergraphs.invariants.structure import is_t_intersecting
>>> H = gc.Hypergraph(E=[{1, 2, 3}, {2, 3, 4}])
>>> is_t_intersecting(H, 2)
True

>>> is_t_intersecting(H, 3)
False

graphcalc.hypergraphs.invariants.transversals.fractional_transversal_number(H: Hypergraph, *, verbose: bool = False, solve=None) → float[source]: Return the fractional transversal number of a hypergraph.

graphcalc.hypergraphs.invariants.transversals.minimum_transversal(H: Hypergraph, *, weights: Dict[Hashable, float] | None = None, verbose: bool = False, solve=None) → Set[Hashable][source]: Return a minimum transversal of a hypergraph.

graphcalc.hypergraphs.invariants.transversals.transversal_number(H: Hypergraph, **solver_kwargs) → int | float[source]: Return the transversal number of a hypergraph.