Throughout the text we have mentioned a number of NP-complete decision problems concerning bipartite graphs. In this appendix we have collected these, together with several others.

Regular subgraph

Instance: A bipartite graph G and a positive integer k ≥ 3.

Question: Does G have a k-regular subgraph?

This problem is NP-complete (see Plesník (1984)).

Embedding a tree in a hyper cube (see p. 39)

Instance: A tree T and an integer n.

Question: Is T a subgraph of the hypercube Qn?

The NP-completeness of this problem was proved by Wagner and Corneil (1990). If we insist that the tree be an induced subgraph, then the problem can be decided in polynomial time (see Djoković (1973)).

Induced matching (see p. 130)

Instance: A bipartite graph G and a positive integer k.

Questin: Is there an induced matching in G of cardinality k?

This problem was proved to be NP-complete by Cameron (1989).

Restricted perfect matching

Instance: A balanced bipartite graph G, positive integers n1, …, nk and subsets E1, …, Ek of E(G).

Questin: Does there exist a perfect matching M such that |M ∩ Ei| ≤ ni for i = 1, …, k?

This problem is polynomially sovable for k = 1 and NP-complete in general (see Itai, Rodeh and Tanimoto (1978))

Matcher

Instance: A simple bipartite graph G with bipartition (V1, V2) where |V1| = |V2| = 2m.