All Questions
Tagged with matching-theory computational-complexity
15
questions
0
votes
1
answer
49
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,468
0
votes
0
answers
8
views
Bipartite Matching With Distant Constraints
I am investigating the complexity of the following problem.
Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
- 9
3
votes
1
answer
88
views
Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?
Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
- 541
2
votes
1
answer
102
views
Multiset Matching
Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
0
votes
0
answers
45
views
What is the order of a sum of arbitrary positive integers?
I am preparing a presentation about a version of Edmond's Blossom Algorithm as it has been
described by William Pulleyblank. The algorithm finds a maximum weight
b-matching for a graph $G = (V, E)$ ...
- 1
2
votes
0
answers
57
views
Variant of Assignment Problem with multiple group constraints
I have a bipartite graph $G = (G_1 \cup G_2, E)$ where we suppose $|G_1| \le |G_2|$.
Each vertex $V \in G_1$ represents a worker. A worker $V$ has two associated values:
a workgroup index $g(V) \in \...
- 21
2
votes
0
answers
210
views
Matching students to courses (easy), but with course-capacities (hard).
I have written a program that matches students to courses, with the following conditions.
A student chooses 12 course-types (biology, art, math, sport, ...).
A course of a type can exist more than ...
- 33
3
votes
1
answer
193
views
Complexity of finding a matching with color constraints in an edge-colored graph with only 2 colors.
Problem
The problem I am considering is the following:
Given: A (multi-)graph $G = (V, E)$ in which each edge is colored either red or blue, and two integers $r$ and $b$.
Determine: Whether a perfect ...
7
votes
1
answer
132
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295
1
vote
1
answer
178
views
Clique cover problem with general clique weights
I consider a graph $G(V,E)$ and each clique has a general weight. The problem is to find a clique cover that maximizes the sum of the weights of the cliques. That is, I want to select a set of cliques ...
- 25
11
votes
4
answers
1k
views
Can you win the monochromatic urn game?
In the (monochromatic) urn depletion game, you are given $n$ vases, each containing some number of balls $a_1,\ldots, a_n \geq 0$. You win the game if you can remove all of the balls from the vases; ...
- 17.7k
1
vote
0
answers
94
views
Cycle plus triangles graph of even order
A cycle plus triangles graph is a 4-regular graph $G$ with a Hamiltonian circuit $C$ and such that the chords of $C$ induce a set of disjoint triangles (3-circuits). Our interest is in these graphs ...
- 405
6
votes
1
answer
2k
views
Maximum "$2$-to-$1$" matching in a bipartite graph
Suppose that we are given a bipartite graph $G$ with bipartition $V(G) = A \mathbin{\dot{\cup}} B$. A $2$-to-$1$ matching in $G$ is a subgraph $M$ such that:
For all vertices $v \in A$, $\deg_{M} v$ ...
- 145k
3
votes
1
answer
2k
views
The determinant and perfect matching.
I have seen the theorem several times that the determinant of the adjacency matrix of a bipartite graph $G$ is not equal to 0 if and only if $G$ has a perfect matching. We can also write this as
$$ ...
- 1,507
1
vote
1
answer
1k
views
Counting all Perfect Matchings in arbitrary graph
Counting the number of perfect matchings in a bipartite graph is known to be difficult, actually #P complete (see a nice math.SE question+answer here).
I was wondering what is known for other graphs? ...
- 924