<p>After some introspection, I'd like to suggest the following natural problem. A  <em>skew-symmetric digraph</em> 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$.</p>

<p>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.</p>

<p>I'm not sure about the practical application of your problem, but I expect it to be P-hard: a reduction from <em>3HornSat</em> 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.</p>

CC BY-SA 3.0
2014-04-16T20:10:47.420Z
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...
Super0
CC BY-SA 3.0
2014-04-16T19:51:19.687Z
2014-04-16T20:02:38.893Z
2014-04-16T20:02:38.893Z
Super0
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-31T17:18:54.693Z
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?
Sasho Nikolov
CC BY-SA 3.0
2014-03-31T17:19:47.703Z
What do you mean by "control of the sexual performances"?
András Salamon
CC BY-SA 3.0
2014-03-31T18:12:18.660Z
@AndrasSalamon: it's just an assumption to justify the problem, this could have several interpretations (videotaping, drug distribution, genetic engineering?) but I'm not sure anything of this happens IRL.
Super0
CC BY-SA 3.0
2014-03-31T18:22:02.537Z
@SashoNikolov: I'm not a biologist so I can't really define what would be "sexual adequacy" and "good/bad unions". Assuming this problem has a real interest, this question should be clarified before proposing a model. Regarding your second question, I expect the adversary would try maximizing its interest, by using a way cleverer strategy than random substitution.
Super0
CC BY-SA 3.0
2014-03-31T20:15:32.847Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2014-04-01T03:39:39.790Z
I disagree with @SashoNikolov on how-to-model-this questions, and agree with this [answer by Scott Aaronson](http://meta.cstheory.stackexchange.com/a/519/1037). 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](http://cogsci.stackexchange.com/).
Artem Kaznatcheev
CC BY-SA 3.0
2014-04-01T04:38:54.253Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2014-04-01T11:36:47.830Z
@SashoNikolov: Fair point, I'll try addressing these issues by (i) reformulating the question in terms of a more interesting "speed-dating" process, (ii) suggesting a possible approach to achieve $P$-completeness through a "cycle packing" formulation. I still have to figure out the details, but stay tuned.
Super0
<multicommodity-flow>
Maximum matching versus preferential assignment
Super0
# Maximum matching versus preferential assignment

(Asked by: username_0 on 2014-03-17)

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.

**Tags:** multicommodity-flow
> **Comments:**
> **username_1**: 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?  
> **username_2**: What do you mean by "control of the sexual performances"?  
> **username_0**: @AndrasSalamon: it's just an assumption to justify the problem, this could have several interpretations (videotaping, drug distribution, genetic engineering?) but I'm not sure anything of this happens IRL.  
> **username_0**: @SashoNikolov: I'm not a biologist so I can't really define what would be "sexual adequacy" and "good/bad unions". Assuming this problem has a real interest, this question should be clarified before proposing a model. Regarding your second question, I expect the adversary would try maximizing its interest, by using a way cleverer strategy than random substitution.  
> **username_1**: @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.  
> **username_3**: I disagree with @SashoNikolov on how-to-model-this questions, and agree with this [answer by Scott Aaronson](http://meta.cstheory.stackexchange.com/a/519/1037). 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](http://cogsci.stackexchange.com/).  
> **username_1**: @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.  
> **username_0**: @SashoNikolov: Fair point, I'll try addressing these issues by (i) reformulating the question in terms of a more interesting "speed-dating" process, (ii) suggesting a possible approach to achieve $P$-completeness through a "cycle packing" formulation. I still have to figure out the details, but stay tuned.  

---

## 1 answers

### Answer by username_0 on 2014-04-16. Score: 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.

> **Comments:**
> **username_0**: 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...  

---

