The Partial Inverse Minimum Connected Spanning Subgraph Problem with Given Cyclomatic Number

摘要

In this paper, we consider a partial inverse problem of minimum connected spanning subgraph with cyclomatic number k. That is, given a subgraph, a cyclomatic number k and a constraint that the edge weights can only decrease, we want to modify the edge weights as little as possible, so that there exists a minimum connected spanning subgraph with cyclomatic number k and containing the given subgraph. For the case that the given subgraph is a connected subgraph with cyclomatic number k, we solve the problem in polynomial time by contracting the subgraph. And when the given subgraph is a spanning tree, we solve the problem in polynomial time by using the MST algorithm.