# Optimization on hypergraph "refinements"

Given a hypergraph $$H = (V, E)$$, call $$H' = (V, E')$$ a refinement of $$H$$ iff there exists a partition $$p : E' \to I$$ (where $$I$$ is an arbitrary index set) such that $$E = \{\bigcup_{x \in p^{-1}(i)} x \mid i \in I\}$$. Essentially this means that there's some way to partition the hyperedges in $$E'$$ such that merging together all the hyperedges in each part of the partition gives $$E$$. Note that this isn't quite the same as just splitting the edges in $$E$$, $$(\{a, b, c\}, \{\{a, b\}, \{b, c\}\})$$ would be a valid refinement of $$(\{a, b, c\}, \{\{a, b, c\}\})$$.

I made up this terminology, is there a name for this in the literature? It seems like a natural concept.

I'm particularly interested in solving a minimization problem where a weighted (i.e.: equipped with a function $$w: E' \to \mathbb{N}$$) hypergraph refinement is the variable, and the set of nodes in the hypergraph is weighted by a function $$c: V \to \mathbb{N}$$ that we'll call the capacity of a node. The only constraint is that the sum of the weights of the hyperedges incident on a given node must be less than or equal to its capacity. The objective function is $$|E'| + |\{v \in V \mid L(v) > 0\}|$$ where $$L(v)$$ is the "leftover weight", the difference between the capacity of $$v$$ and the sum of incident hyperedge weights, i.e.: $$L(v) = c(v) - \Sigma_{e \in E', v \in e} w(e)$$. The constraint is then formally stated as $$L(v) \ge 0$$ for all $$v \in V$$. Intuitively, this is like a combination of a minimum cover problem with a subset-sum on each node.

Is any of this secretly equivalent to something else?

For context, I'm trying to solve this problem where the hypergraph came from the maximal cliques of a graph (i.e.: we're really trying to find weights for each clique in a graph such that the sum of the incident cliques' weights is less than a per-node constant).

• $E'$ isn't a partition -- it's a set of new hyperedges such that there exists a partition of the hyperedges where merging all the hyperedges in each part together gives you $E$. The number of hyperedges incident on any particular node is definitely not 1, and can only be increased by the choice of refinement (note that the new edges in $E'$ need not be disjoint). Jan 24, 2022 at 21:41
• It may help to think about where this abstraction came from. We want to assign weights to every clique in a graph. $E$ is the set of maximal cliques. $E'$ is the set of cliques with nonzero weights. Jan 24, 2022 at 21:44
• Unfortunately any approach like that is too brittle to changes in the objective function for me; it would break if the objective function were $\lambda |E'| + |\{v \in V \mid L(v) > 0\}|$ for $\lambda \neq 1$, for example, which is probably closer to what I actually want to optimize. In general the thing I really want to optimize is probably closer to $f(E') + g(\{v \in V \mid L(v) > 0\})$ where $f$ and $g$ are submodular set functions, but a solution to the version with $\lambda$ would be a decent approximation in practice. Jan 27, 2022 at 9:03