1
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ Sounds like there might be an interesting question there, but I do not understand the model. Can you be more formal about it? If you are saying an adverasy with limited computational ability can modify the input to a matching problem, then wouldn't an adversary that substituted random weights for the true weights be very simple and break everything very badly? $\endgroup$ – Sasho Nikolov Mar 31 '14 at 17:18
  • 2
    $\begingroup$ What do you mean by "control of the sexual performances"? $\endgroup$ – András Salamon Mar 31 '14 at 17:19
  • 5
    $\begingroup$ @Super0 This site is designed for well-defined questions with objective answers. A "how do I model this?" is IMO too discussion based for CSTheory@SE. If you want to ask a question here, I recommend that you pick a precise formulation of your model and the problem. Otherwise, you'd be better off looking for another forum for this. Again, this does not mean it's not a good question, but it doesn't seem suited to this site in its current form. $\endgroup$ – Sasho Nikolov Mar 31 '14 at 20:15
  • 2
    $\begingroup$ I disagree with @SashoNikolov on how-to-model-this questions, and agree with this answer by Scott Aaronson. That being said, in the case of this post, it is (in my opinion) just a poorly worded question and doesn't seem to genuinely be trying to model something. I think most people realize the marriage story told when introducing matching algorithms is just for fun, and nobody actually models mate selection this way. If OP is actually interested in the social science question then I recommend CogSci.SE. $\endgroup$ – Artem Kaznatcheev Apr 1 '14 at 3:39
  • 5
    $\begingroup$ @Artem Of course I agree that modeling is an important part of theory of computing. But IMO something on the level of "here are a bunch of observations, make me a model" would be a very bad fit for CST@SE. Unless the question already shows the "shape" of a model and asks for a specific issue, I do not see it faring well. $\endgroup$ – Sasho Nikolov Apr 1 '14 at 4:38
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ However, I'm afraid that we're out of luck in case one of the 'twin vertices' is missing, as then it is impossible to match the other twin according to this definition. We might have to relax the definition if we are willing to be more 'pragmatic' - though it depends on your interpretation of the word... $\endgroup$ – Super0 Apr 16 '14 at 20:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.