Skip to main content
14 votes
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 ...
Neal Young's user avatar
  • 10.8k
12 votes

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 ...
Bart Jansen's user avatar
  • 5,275
10 votes
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,...
Peter Shor 's user avatar
10 votes
Accepted

What is the connection between moments of Gaussians and perfect matchings of graphs?

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $...
Yury's user avatar
  • 3,909
9 votes

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. Later the base of the ...
domotorp's user avatar
  • 14k
7 votes
Accepted

Can we decide whether a permanent has a unique term?

EDIT - 2/11/20 - barring mistakes, this should answer the posted question. Summary. Define a new complexity class, UW-NP, containing languages definable as follows: given any poly-time non-...
Neal Young's user avatar
  • 10.8k
7 votes
Accepted

Does Horn SAT (Horn formula in CNF) have an integral polytope?

EDIT: Strengthened Theorem 2. The answer to the problem as posed is no, unless P=NP: Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is ...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

What is the complexity of this weighted b-edge matching problem?

Assuming $x(e)=1$ in Condition 2, the problem is NP-complete. Clearly it is in NP. We show NP-hardness by reduction from Subset Sum: Lemma 1. The problem is NP-hard. Proof. The proof is by the ...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

Min weight perfect matching with even number of red edges

The problem is polynomial time solvable. After discussing with Vivek Madan, we can show that the proof of Theorem 5.1 in Perfect Matching in Bipartite Planar Graphs is in UL works in the weighted ...
Chao Xu's user avatar
  • 4,479
5 votes

What is the connection between moments of Gaussians and perfect matchings of graphs?

Here is a different proof, adapted from the monograph The semicircle law, free random variables and entropy. Let $X_i$ be an infinite sequence of i.i.d. variables with distribution $\Pr[X_i = 1] = \Pr[...
Yuval Filmus's user avatar
  • 14.5k
5 votes
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 ...
Cyriac Antony's user avatar
5 votes
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 ...
Tassle's user avatar
  • 881
4 votes

Graph factors of maximum weight

The case where all gaps have the same parity was solved by Jácint Szabó. There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They claimed to have solved the problem.
Chao Xu's user avatar
  • 4,479
4 votes
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 ...
Heng Guo's user avatar
  • 375
4 votes

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 ...
mhum's user avatar
  • 3,392
4 votes
Accepted

Bipartite matching with degree domination

There does not always exist a matching with your property in a bipartite graph. Consider for example the graph $G = (V, E)$ where $V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$ and $...
Mikhail Rudoy's user avatar
4 votes
Accepted

Is Permanent $+$-reducible?

If you allow weighted edges and weighted perfect matchings (instead of just counts), then yes. I don't know a "nice" clean graph-theoretic description, but in principle one can be extracted ...
Joshua Grochow's user avatar
4 votes

Is perfect matching for bipartite graph with no cycles unique?

If the graph is acyclic, which implies that it is also bipartite, then the perfect matching is unique by the following algorithm: While the graph is not empty, pick a leaf vertex $u$ (which exists ...
Christian Komusiewicz's user avatar
4 votes
Accepted

Maximum cardinality matching on DAGs

A matching that lies on a path of length (number of edges) $m$ has at most $m+1$ vertices, and therefore at most $\lceil m/2\rceil$ edges; conversely, such a path does include a matching with $\lceil ...
Emil Jeřábek's user avatar
4 votes

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-...
Magnus Wahlström's user avatar
3 votes
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 ...
David Eppstein's user avatar
3 votes
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.$...
yangpliu's user avatar
  • 169
3 votes
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 ...
Yuval Filmus's user avatar
  • 14.5k
3 votes
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 ...
JimN's user avatar
  • 1,318
2 votes
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 ...
usul's user avatar
  • 7,615
2 votes
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). $$ ...
George Octavian Rabanca's user avatar
2 votes
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 ...
Hiroki Yanagisawa's user avatar
2 votes
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 \}$ ...
Marzio De Biasi's user avatar
2 votes
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 ...
Tassle's user avatar
  • 881
2 votes
Accepted

Maximum weight matching with surreal weights

Fix any algorithm that works for integer edge weights, and treats the weights as black boxes that can be copied, added, subtracted, and compared, but cannot be accessed in any other way. Furthermore, ...
Emil Jeřábek's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible