Maximum matching versus preferential assignment

Question

There are several ways to solve the marriage problem. The "preferential assignment" approach consists in forming couples on the basis of preferred characteristics expressed by each individual. An alternative approach consists in selecting preferred partners among lovers: suppose that you have the graph $G$ of sexual relations, and that each relation $e$ is rated with some preference factor $w(e)$, then computing a maximum weighted matching in $G$ would aim at optimizing the sexual adequacy between lovers.

If there are only heterosexual relationships with two sexes (men and women), then this is a bipartite matching problem, which is conjectured to be in $NC_2$ . Now suppose that a devious adversary had the following abilities: (i) control of the sexual performances of the individuals, (ii) ability to solve parallel problems efficiently. Then this adversary could trick the heterosexual group into forming "bad unions" in a pessimistic sense, i.e. leading to increased instability or corruption.

So my question is: what are the remedies to this problem? Does the introduction of same-sex relations or ternary relations change the situation? I suspect that the goal would be to obtain a P-complete matching problem to defeat the parallel adversary.

Answer 1

After some introspection, I'd like to suggest the following natural problem. A skew-symmetric digraph is a digraph $G$ where each vertex comes in two copies $v,v'$ (possibly identical) and such that for each arc $(u,v) \in A(G)$ we also have $(v',u') \in A(G)$. The problem consists of packing cycles in a skew-symmetric digraph under a weight constraint. That is to say, we are given a ssd $G = (V,A)$, a weighting $w : V \rightarrow \mathbb{N}$ s.t. $w(v') = w(v)$ for each $v \in V$, and an integer $k$, and we seek a family of $k$ cycles $\cal{C}$ in $D$ such that (i) $V(\cal{C})$ has maximum cardinality, (ii) each $C \in \cal{C}$ is skew-symmetric, i.e. if it contains $(u,v)$ then it also contains $(v',u')$, (iii) each vertex $v$ is contained in at most $w(v)$ cycles of $D$.

This problem would generalize two well-known problems in combinatorial optimizations: (1) maximum matchings in undirected graphs and (2) maximum $k$-chains in posets. Here is a sketch of the reductions. For problem (1) we start with an undirected graph $G$, and we let $D$ be the symmetric digraph obtained from $G$ with each vertex self-symmetric, assigning a weight one to each vertex. For problem (2) we start with a poset $P_0$ with underlying digraph $D_0$, and we let $D$ be the digraph obtained by taking the disjoint union of $D_0$, its symmetric copy, and arcs $(v,v'), (v',v)$ for each vertex $v$ of $P$; we assign a weight one to each vertex.

I'm not sure about the practical application of your problem, but I expect it to be P-hard: a reduction from 3HornSat to the weighted version seems possible although I didn't check the details. If this problem turned out to be in P (with a corresponding min/max result) it would be very interesting, at least from a theoretical standpoint.