Some Graph Optimization Problems with Weights Satisfying Linear Constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including the maximum matching problem under linear constraints (max-MLC), the minimum perfect matching problem under linear constraints (min-PMLC), the shortest path problem under linear constraints (SPLC) and the vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and to find the optimal solution of the graph optimization problems among all the feasible choices of weights. Even though all the original graph optimization problems can be solved in polynomial time or be approximated within a fixed constant factor, we find that these problems under linear constraints are intractable in general. In particular, we show that the max-MLC problem is NP-hard, while the min-PMLC, SPLC, VCLC problems are all NP-hard and do not even have any polynomial-time algorithms unless \(P = NP\). These findings suggest us to explore the special cases of these problems which are tractable. Particularly, we show that when the number of constraints is a fixed constant, all these problems under linear constraints are polynomially solvable. Moreover, if there are fixed number of distinct weights, then the max-MLC, min-PMLC and SPLC are polynomially solvable, and the VCLC has 2-approximation algorithm. In addition, we propose several approximation algorithms for max-MLC.