# 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 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 at 21:44
• Will an NP-hardness proof answer your question? Jan 25 at 13:25
• Polynomially reducing it to some other solvable in practice NP hard problem, like integer linear programming, would be helpful (naive ILP doesn't work because there are exponentially many cliques) Jan 25 at 21:15
• 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 at 9:03