# Tag Info

21

Markov proved that any function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the result from the GLL blog. More precisely: Theorem: Suppose $f : \{0,1\}^n \to \{0,1\}^m$ is computed by a circuit $C$ with $g$ gates, then it is also computed ...

19

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution." For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual ...

18

An upper bound on the maximum number of stable matchings for a Stable Marriage instance is given in my Master's thesis and it is extended to the Stable Roommates problem as well.The bound is of magnitude $O(n!/2^n)$ and it can be shown that it is actually of magnitude $O\left((n!)^\frac{2}{3}\right)$. The document is thesis number 97 on page http://mpla....

13

The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete. This has been proved by Les Valiant himself, on page 415 of the paper Leslie G. Valiant The Complexity of Enumeration and Reliability Problems SIAM J. Comput., 8(3), 410–421

12

No. Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a',b',c'\}$ and the other one with the nodes $\{d,e,f\} \cup \{d',e',f'\}$. Remove the edges $(c,c')$ and $(d,d')$. Add the edges $(c,d')$ and $(d,c')$.

12

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 Mulmuley, Vazirani, and Vazirani. It has been useful for similar applications in the past, see for example Proposition 9 and the preceding discussion in Daniel ...

10

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, let's notice that for $b_n=a_{2^n}$, we have the recurrence $$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$ Now, let's assume that $b_n = r s^{2^n}$. The equation ...

9

The answer is NOT $\lceil \frac{mn}2\rceil$ for all large $m, n$ if e.g. $p=6$ and $q=3$. Why? Notice that because of the remainders $\mod 3$ now the graph is the (vertex) disjoint union of three bipartite graphs and from each we can select the bigger half. For example if $m=n=100$, then this way we can place (at least) 5002 knights. (This is because $x+y \... 9 I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec Divide the vertices into two groups - some will represent literals, the ... 9 This is a combination of comments from me and Chandra Chekuri above, elaborated a bit. As background, if you have a partial matching then its symmetric difference with the optimal matching can be decomposed into disjoint alternating paths (and possibly also some alternating cycles but those can be ignored). Hopcroft–Karp maintains a partial matching as it ... 9 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$c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$be the covariance of$\gamma_i$and$\gamma_j$. Consider the complete graph on$\{1, \dots, 2n\}$; assign weight$c_{...

8

Our recent paper shows that counting k-matchings is #W-hard even in bipartite graphs. This answers your question. Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)

8

Here is an attempt to prove that the problem without the reverse condition is NP-hard. The basic idea is that disjoint intervals in $S$ like this one: [S] +-a-+ +-b-+ +---c-----+ c<a, c<b (here < is interval inclusion) can have a valid mapping to a "pyramid" in $T$: [T] +-x-+ f(a)=x, f(b)=y, f(c)=z +-y---+ +-z-----...

7

As an expansion of the comment I made above, here it is in answer form. I'll just talk about maximum matchings, since that will demonstrate the point. Suppose that we consider both $K_{1,2n-1}$ and $K_{n,n}$. The first has a maximum matching of size 1, since it's a star graph, and the other has $n$ for obvious reasons. It's easiest to reason about the ...

7

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.

7

There is a totally different algorithm due to Subramanian which uses a fixed point approach. The first idea is to represent the knowledge that we have at any given point in time using intervals, which represent which women each man is considering, and vice versa. Using ideas similar to Gale-Shapley, we keep shrinking the intervals. In contrast to Gale-...

7

You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf but more optimizations are possible). These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so ...

6

The stable marriage problem with ties (a matching problem for bipartite graphs) is (trivially) solvable in polynomial time, whereas the stable roommate problem with ties (a matching problem for general graphs) is known to be NP-hard. See Eytan Ronn: NP-Complete Stable Matching Problems. J. Algorithms 11(2): 285-304 (1990) for details.

6

Switching from 2 to 3 "beds" makes the problem NP-complete :-) See K. Iwama, S. Miyazaki, and K. Okamoto, "Stable roommates problem with triple rooms." Proc. 10th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007), pp. 105–112, 2007 (an electronic edition can be downloaded from ResearchGate). Abstract: In the stable roommates problem, we ...

6

Yes, there is a polynomial-time algorithm to find any stable matching. Understanding the algorithm requires you to study a rotation poset. One of the good materials to learn the rotation poset is this book. Dan Gusfield, Robert W. Irving: The Stable marriage problem - structure and algorithms. Foundations of computing series, MIT Press 1989

6

The problem can be solved in $O(n^k \, \text{poly}(n))$ time, so it's not "NP-hard in $n$" unless P=NP. Here's one simple algorithm. Enumerate all subsets $E'$ of $E$ such that $|E'|\le k$. Check whether the union of labels of $E'$ is equal to $\{1,2,\dots,k\}$; if not, move on to the next candidate for $E'$. Then, check whether there's a perfect ...

5

Firstly note that: given a graph $G=(V,E)$, two distinguished vertices $s,t \in V$ and an integer $k$, the problem of deciding whether there are $k$ internally vertex-disjoint odd-length paths between $s$ and $t$ is polynomially equivalent to deciding whether there exists $k$ even-length paths between $s$ and $t$. The reduction is easy. To reduce from one ...

5

If all edge weights are non-negative, then the minimum weight set of edges that covers all the nodes automatically has the property that it has no three-edge paths, because the middle edge of any such path would be redundant. If we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others ...

5

Yes, cause the problem lies in P. Look at paper Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''

5

The problem is in RP in both (A) and (B) by a variation of Lovasz's algorithm: Fix a finite field $F$ of characteristic $2$ on at least $q=4m\max_i |a_i|$ elements. Consider the graph's Tutte matrix $T(r)$ where you replace indeterminate $x_{ij}$ by $y_{ij}r^{a_{ij}+q/4}$, where $y_{ij}=y_{ji}$ is a uniformly and independently randomly chosen element in $F$ ...

5

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 conjecture. See the chapter "Connected Matchings" by Cameron in the book "Combinatorial Optimization – Eureka, You Shrink!" The status of connected matchings in ...

5

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 context too (their result is to decide if there is a feasible solution). Let $R$ be the set of even edges. Let $M$ be a minimum weight perfect matching. If $|M\... 4 There is also a small set of linear constraints that form a polytope whose extreme points are the stable matchings. This allows you to find a stable matching optimizing any linear objective using linear programming. See Vande-Vate 89 ("Linear Programming Brings Marital Bliss"), or Vohra 12 for a different treatment ("Stable Matchings and Linear Programming") 4 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 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$E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}\$ ...

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