I'm doing a C++ project that requires solving the Assignment Problems. During the study of the subject I have a doubt, is it possible that in any assignment problem, one or more arcs that connect any pair of left and right vertices are not there?
Let me explain better, taking into consideration the cost matrix is it possible that some cells are equal to zero to indicate the absence of an arc that connects a left vertex to a right vertex?
Or Does it necessarily have to be that in the assignment problems in the bipartite graph every vertex must be connected to every vertex of the opposite side and therefore have a positive cost?
Thanks for the help!
In practice, there is no requirement that every possible arc exist. Note, though, that if not all arcs exist it might be impossible to form a complete assignment (meaning the problem might be infeasible).
Textbooks will typically assume a complete bipartite graph (all possible arcs present) when defining the assignment problem, so this may be a gray area of terminology. If you want to confine yourself to the textbook definition, an alternative to omitting an arc would be to include it with a cost so large that it would be prohibitively costly to select that arc. (If the arc is selected anyway in an optimal solution, then omitting the arc makes the problem infeasible.)