A linear programming formulation for the maximum complete multipartite subgraph problem

摘要

Let G be a simple undirected graph with node set V (G) and edge set E(G). We call a subset F subset of E( G) independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper we characterize the independents and the minimal dependents of G. We note that every minimal dependent of G has size two if and only if G is fan and prism-free. We give a 0-1 linear programming formulation of the following problem: find the maximum weight of a complete multipartite subgraph of G, where G has nonnegative edge weights. This formulation may have an exponential number of constraints with respect to vertical bar V(G)vertical bar but we show that the continuous relaxation of this 0-1 program can be solved in polynomial time.