Tag Info

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

10

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a ...

9

The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even. Given $G=(L\cup R, E)$, we construct a new graph $G'=(V',E')$ as follows, let $|R|=n$. Add vertices in $R$ to $V'$. For each vertex $v \in L$, add vertices $v_1,... 7 Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in: Gilles Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees, The Electronic Journal of Combinatorics 4(1), ... 6 For an extreme example, chordal graphs can have as many as$\binom{n}{2}$edges but chordal graphs that happen to also be bipartite can have only$n-1$edges (they are forests). Or even more extremely, consider complete graphs versus (complete$\cap$bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are ... 4 According to the 59th slide of the following pdf: https://grow2015.sciencesconf.org/file/174789 (A talk by D.Kratsch at GROW 2015) we have that A vertex in a graph is weakly simplicial if its neighborhood is an independent set and the neighborhoods of its neighbors form a chain under inclusion. See the slide for an illustration. The context where ... 4 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 because the graph is acyclic) add the edge between$u$and its unique neighbor$v$to the matching and then remove$u$and$v$. If at some point graphs without ... 4 Your problem is NP-hard. Consider a partition problem instance with input$a_1,\ldots,a_n$. We create a complete bipartite graph with$2$source vertices each with capacity$\frac{1}{2} \sum_{i=1}^n a_i$, and$n$sink vertices, where the$i$th vertex has capacity$a_i$. Each edge has infinite capacity. It's easy to verify there is a partition with equal ... 4 The following is a list of results I'm going to prove: if$k$and$l$are parts of the input and$d = 1$is a fixed constant then the problem is polynomial time solvable if$k$and$l$are parts of the input and$d \ge 2$is a fixed constant then the problem is NP-complete if$k$is a fixed constant then the problem is polynomial time solvable if$l$is a ... 4 Consider a graph on vertex set$V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$where$|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set$E$is covered by$C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$. When$n$is large enough, any minimalist cover must contain the four maximum cliques$V_1\cup\{a,c\}$and so on, so it is not hard ... 3 ...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions. Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p 3 An$r$-regular expander should do it. The following is a simple observation that I first saw in Li (arXiv:2106.05513): if an$r$-regular graph has conductance$\phi$, then the smaller side$S$of a minimum cut contains at most$|S| \leq 1/\phi$vertices. Indeed, by definition of conductance we have that$|E(S,S^c)| \geq \phi r |S|$. Since this defines a ... 3 This problem is a special case of the b-matching problem, and hence can be solved in polynomial time. Extensive information on b-matchings can be found for instance in the book: László Lovász and Michael D. Plummer: Matching Theory ISBN-10: 0-8218-4759-7 ISBN-13: 978-0-8218-4759-6 3 In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers$p$and$q$with$q\ge p-1$a way to construct a graph with$p$vertices and$q$edges that is$k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from$0$to$p-1$to the$p$vertices and then add edges between vertices whose ... 3 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 perfect matching has just one perfect matching". The same paper provides a more general characterization of the bipartite graphs with a unique perfect ... 3 In case anyone else is looking for a practical answer: the program plantri by Brinkmann and McKay can generate small (up to 64 vertices as-is, up to 255 with some hacking) planar bipartite cubic graphs as the duals of Eulerian planar triangulations. The program does not sample uniformly at random, but it is claimed to be efficient enough to generate all ... 3 You can take any degree 3 bipartite graph$G$and take its disjoint union$G'$with a cycle$C$of length 2m. The new graph$G'$is bipartite, and has average degree$\frac{3n + 2m}{m+n} = 2 + \frac{n}{n+m}$. Also, the number of perfect matchings in$G'$is exactly twice the number of perfect matchings in$G$, because the perfect matchings of$G'$are the ... 2 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 Time Local Approximation Algorithm for Maximum Stable Marriage, Algorithms 2013, 6, 471-484. There are many papers on MAX SMTI, but unfortunately I am not aware ... 2 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 problem only with all capacities equal to one. My best guess is that you will have to do some work to extend their guarantees and algorithm to your setting. On the ... 2 The precoloring extension problem is the following: Input: a number$k$and a graph$G$some of whose edges are labeled with labels in$\{1, 2, \ldots, k\}$. Decision: is it possible to color the edges of$G$with colors$1, 2, \ldots, k$such that no adjacent edges share a color and such that each initially labeled edge is colored with the color it is ... 1 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 B\cup C = \{a_1,b_1\}\cup\{a_2,b_2\}\cup\{c_1\}\cup\{c_2\}$. 1 My two cents: The worst case of building$G_\top$is in$\Omega(n^2)$time and space: assume$\bot$contains a single node linked to all nodes in$\top$. Maybe you are not looking for a worst case complexity? Then,$O(\sum_{u\in\bot}(d_u)^2)$time to build$G_\top$by listing all edges$u,v$such that$u$and$v$are neighbors of the same node in$\bot$. ... 1 If$G$has a disjoint vertex cycle cover then I agree that$H$must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define$H$exactly). I think the construction you were thinking of is the one described in this answer: https://cstheory.stackexchange.com/a/8570/38111. As for your question (assuming that$H$is ... 1 After some thinking, I found an answer. If one has a better one I'll accept it. From a cost matrix of shape$n\times m$with$n<m$, it is easy to add nodes that will not change anything by giving all their incident edges the same weight$w$, that is adding$(m-n)*m$edges. 1 Yes, there certainly is. There is a trivial solution. First, solve the resource allocation problem (which can be done in exponential time by enumerating all candidate solutions). Then, use the solution to construct a bipartite graph whose maximum-weight matching corresponds to the solution in some way; this is straightforward. Finally, output that graph. ... 1 I believe "maximum weight fair bipartite matching" as you've defined it is NP-hard. Even more, determining the existence of a fair bipartite matching is NP-hard. Before I give a proof sketch, for intuition, consider the following small instance. Take$G'=(L, R, E'=L\times R)$where$L=\{a,b\}$,$R=\{c,d,e,f\}$. Take$p$such that$p(u,w) = 0$for$u\in ...

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