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).

  • $\begingroup$ $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). $\endgroup$
    – taktoa
    Jan 24 at 21:41
  • $\begingroup$ 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. $\endgroup$
    – taktoa
    Jan 24 at 21:44
  • $\begingroup$ Will an NP-hardness proof answer your question? $\endgroup$
    – D Goyal
    Jan 25 at 13:25
  • 1
    $\begingroup$ 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) $\endgroup$
    – taktoa
    Jan 25 at 21:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – taktoa
    Jan 27 at 9:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy