<p>Given a bipartite graph $G$ with node set $(X+Y)$. Each node $x \in X$ has to be assigned to 1 node $y \in Y$. Assignment is only possible if there is an edge between $x \in X$ and $y\in Y$. Furthermore, each node $y\in Y$ can only handle $d_y$ assignments.</p>

<p>Let us assume that for a given graph such an assignment is not possible. Now I would like to compute the minimum induced subgraph of $G$ which is still infeasible. Are you aware of any related problems, or pointers on how to solve this efficiently?</p>

<p>Example. Given the graph below, and the following weights: $d_a=3, d_b=2, d_c=d_d=1$</p>

<pre><code>1 - a
  /
2 - b
  \
3 - c
  /
4

5 - d
</code></pre>

<p>There does not exist an assignment of the nodes 1-5 to a-d. Clearly we can remove nodes 5, d from the graph because the resulting subgraph is still infeasible. Similarly we can remove the nodes 1,a,2,b. The minimum induced infeasible subgraph here is composed of the nodes 3 and 4 and c . How can I compute this efficiently?</p>

<p>Very much related is the following problem:</p>

<p>$max \sum_{i\in X}x_i-\sum_{j\in Y}d_jy_j$<br>
$y_j \geq x_ie_{ij} \;\;\;\forall i\in X,j\in Y$<br>
$x_i,x_j\in \{0,1\}$</p>

<p>Here $x_i$ is a variable indicating whether we take a vertex from partition X. Similar for $y_j$. $e_{ij}$ is a parameter indicating whether there is an edge between $i\in X$ and $j\in Y$. Note that when $x_i=1$, then all neighbors of $i$ in partition $Y$ are also 1. $d_i$ is the supply provided by node $i\in Y$. Is this integer program a known combinatorial optimization problem?</p>

CC BY-SA 3.0
2012-03-08T15:18:32.047Z
Your definition of a matching seems to be a little off. Typically for a bipartite graph $G=(A,B,E)$ any subset $I \subseteq A$ must have at least $|I|$ neighbors in $B$ for there to exist a matching.
Nicholas Mancuso
CC BY-SA 3.0
2012-03-08T15:55:58.360Z
You are correct in that. I edited the title as this problem is closer to an assignment problem than to a matching problem
Joris
CC BY-SA 3.0
2012-03-08T16:26:31.867Z
Essentially you're asking for a generalization of finding a minimum sized Hall witness. Interesting.
Suresh Venkat
CC BY-SA 3.0
2012-03-09T09:01:56.433Z
It seems to me you could turn it into a "real" matching problem by making $d_y$ copies with identical neighborhoods of every vertex $y \in Y$, and looking for a matching which saturates all of $X$ in the resulting graph. As Suresh points out, Hall's Theorem tells you what the obstructions to having a matching  look like. This might not be entirely what you want, as a minimum-size Hall obstruction for the matching minimizes the number of vertices in the blown-up graph rather than in the original.
Bart Jansen
CC BY-SA 3.0
2012-03-11T00:04:36.500Z
You need to decide what you mean by "minimum".  As I see it, the sensible definition is to minimize the size of $X'\subseteq X$, let $Y'$ be the neighbourhood of $X'$, and subject to $X'$, minimize $\sum_{y\in Y'}(\min\{d(y),d_y\})$.
Andrew D. King
<ds.algorithms><graph-theory><graph-algorithms>
Minimum infeasible subgraph in assignment problem
Joris
# Minimum infeasible subgraph in assignment problem

(Asked by: username_0 on 2012-03-08)

Given a bipartite graph $G$ with node set $(X+Y)$. Each node $x \in X$ has to be assigned to 1 node $y \in Y$. Assignment is only possible if there is an edge between $x \in X$ and $y\in Y$. Furthermore, each node $y\in Y$ can only handle $d_y$ assignments.
Let us assume that for a given graph such an assignment is not possible. Now I would like to compute the minimum induced subgraph of $G$ which is still infeasible. Are you aware of any related problems, or pointers on how to solve this efficiently?
Example. Given the graph below, and the following weights: $d_a=3, d_b=2, d_c=d_d=1$
1 - a
  /
2 - b
  \
3 - c
  /
4

5 - d

There does not exist an assignment of the nodes 1-5 to a-d. Clearly we can remove nodes 5, d from the graph because the resulting subgraph is still infeasible. Similarly we can remove the nodes 1,a,2,b. The minimum induced infeasible subgraph here is composed of the nodes 3 and 4 and c . How can I compute this efficiently?
Very much related is the following problem:
$max \sum_{i\in X}x_i-\sum_{j\in Y}d_jy_j$
$y_j \geq x_ie_{ij} \;\;\;\forall i\in X,j\in Y$
$x_i,x_j\in \{0,1\}$
Here $x_i$ is a variable indicating whether we take a vertex from partition X. Similar for $y_j$. $e_{ij}$ is a parameter indicating whether there is an edge between $i\in X$ and $j\in Y$. Note that when $x_i=1$, then all neighbors of $i$ in partition $Y$ are also 1. $d_i$ is the supply provided by node $i\in Y$. Is this integer program a known combinatorial optimization problem?

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Your definition of a matching seems to be a little off. Typically for a bipartite graph $G=(A,B,E)$ any subset $I \subseteq A$ must have at least $|I|$ neighbors in $B$ for there to exist a matching.  
> **username_0**: You are correct in that. I edited the title as this problem is closer to an assignment problem than to a matching problem  
> **username_2**: Essentially you're asking for a generalization of finding a minimum sized Hall witness. Interesting.  
> **username_3**: It seems to me you could turn it into a "real" matching problem by making $d_y$ copies with identical neighborhoods of every vertex $y \in Y$, and looking for a matching which saturates all of $X$ in the resulting graph. As Suresh points out, Hall's Theorem tells you what the obstructions to having a matching  look like. This might not be entirely what you want, as a minimum-size Hall obstruction for the matching minimizes the number of vertices in the blown-up graph rather than in the original.  
> **username_4**: You need to decide what you mean by "minimum".  As I see it, the sensible definition is to minimize the size of $X'\subseteq X$, let $Y'$ be the neighbourhood of $X'$, and subject to $X'$, minimize $\sum_{y\in Y'}(\min\{d(y),d_y\})$.  

---

## 0 answers

