5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nicholas Mancuso Mar 8 '12 at 15:18
  • $\begingroup$ You are correct in that. I edited the title as this problem is closer to an assignment problem than to a matching problem $\endgroup$ – Joris Mar 8 '12 at 15:55
  • 1
    $\begingroup$ Essentially you're asking for a generalization of finding a minimum sized Hall witness. Interesting. $\endgroup$ – Suresh Venkat Mar 8 '12 at 16:26
  • $\begingroup$ 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. $\endgroup$ – Bart Jansen Mar 9 '12 at 9:01
  • $\begingroup$ 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\})$. $\endgroup$ – Andrew D. King Mar 11 '12 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.