# Tag Info

Accepted

### Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing ...
• 10.8k

### Min weight perfect matching with even number of red edges

I think your problem is solvable in randomized polynomial time, if the weights are bounded polynomially in the size of the graph. You can use an approach based on the algebraic matching algorithm by ...
• 5,275
Accepted

### The asymptotic behavior of a recurrence related to stable matchings

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily. First,...
• 24.8k
Accepted

• 14.5k
Accepted

### Maximum matching M with the condition G[M] is 2K_2-free

Surprise! (for me). This type of matchings are already studied in the literature. They are called connected matchings. They were introduced by Plummer, Stiebitz and Toft in their study on Hadwiger ...
• 1,797
Accepted

### Number of stable matchings

Yes. Thurber showed [1,Theorem 5] that for all $n\geq 1$, the maximum number of stable matchings is at least $\frac{(2.28)^n}{(1+\sqrt{3})^{1+\log_2 n}}$. If I'm not mistaken this is strictly greater ...
• 881

### Graph factors of maximum weight

The case where all gaps have the same parity was solved by Jácint Szabó. There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They claimed to have solved the problem.
• 4,479
Accepted

### Complexity of Uniform Generation of Perfect Matchings

The Jerrum-Sinclair-Vigoda algorithm can be used to sample perfect matchings approximately in bipartite graphs. For general graphs, as far as I know, sampling perfect matchings (approximately or ...
• 375

### Complexity of Uniform Generation of Perfect Matchings

In [1], the author presents an acceptance/rejection algorithm for generating a uniform sample from the set of perfect matchings of a bipartite graph. While the samples are exactly uniform regardless ...
• 3,392
Accepted

• 17.9k

### Weighted bipartite matching with no-cycle constraint

Claim: A matching $M$ has a cycle-free residual graph if and only if the graph $G[V(M)]$ induced on its vertex set has a unique perfect matching. Given this, the problem is at least as hard as 2-...
Accepted

### Is perfect matching for bipartite graph with no cycles unique?

This fact can be found in Godsil, C. D. (1985), "Inverses of trees", Combinatorica 5 (1): 33–39, doi:10.1007/BF02579440 (without proof, near the bottom of the first page): "noting that a tree with a ...
• 51.1k
Accepted

### Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $A, B$ be the bipartition of $G$ and $|A| = |B| = n.$ Claim: $c_1 + c_2 + c_3 \equiv n \pmod{2}.$ To show this, we can naturally associate each matching $M_i$ to a permutation $\sigma_i \in S_n.$...
• 169
Accepted

### Almost regular subhypergraph of hypergraph with large minimal degree

Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$. Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 > 0$. Consider a ...
• 14.5k
Accepted

### Are there any results on the following "generalized matching" problems?

In http://www.sciencedirect.com/science/article/pii/S0012365X13003543 , we use exactly this process of picking the largest possible clique, then the next largest available clique, and so on (without ...
• 1,318
Accepted

### Online/approximate weighted and capacitated bipartite matching

I think there is no paper solving that exact problem, but "Online Vertex-Weighted Matching" by Aggarwal, Goel, Karande, and Mehta (2011) is very close. If I understood correctly, they solve your ...
• 7,615
Accepted

### Maximum weight matching and submodular functions

Definition. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that: $$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).$$ ...
Accepted

### Maximum stable matching/allocation

Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). You can find the current best approximation algorithm for MAX SMTI in the following paper: Z. Kiraly, Linear ...
Accepted

### 3-dimensional matching variant

No, the variant is in P: for each element $x_i \in X$ find the set $A_{x_i}$ of triples "reachable" from $x_i$: start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$ ...
Accepted

### Do such instances always admit a 3D matching?

How about the following counter-example? $m=2$, $n=4$. $A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$. $T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$. With the partition \$A\cup ...
• 881