eldorado.tu-dortmund.de/server/api/core/bitstreams/35dd3ec1-8ebf-443f-b970-76fbf17dc2e7/content
Bulk-Robust Assignment Problems: Hardness, Approximability and Algorithms
+ (2, 3, 4, 5, 6, 7, 8) (black),
G2 := G1 + (2, 5) (gray),
G3 := G2 + (1, 3) + (2, 8) (blue),
G4 := G3 + (4, 9, 10, 6) (green).
Note that adding only one of the ears (1, 3) or (2, 8) to the graph G2 does [...] APX-hard with respect to the AP-reducibility (see [Aus+12, Def. 8.3]) which is commonly used to define APX-hardness (see [Aus+12, Def. 8.5]). Since L-reductions are easier to handle, we omit further details [...] ([Plu86, Thm. 2.2]8). Let G = (U ∪̇W,E) be a bipartite connected graph and k 6 |V(G)|−2
2 . Then the graph G is k-extendable if and only if |U| = |W| and
∀ ∅ 6= T ( U : |T |+ k 6 |NG(T)|.
8 According to [Plu86] …
