Maximum max-k-clique subgraphs in cactus subtree graphs.

In this paper, we analyze the intersection graphs of subtrees in a cactus, called cactus subtree graphs. A max-k-cliquesubgraph of a graph is an induced subgraph whose maximum clique has at most k vertices. We describe a polynomial time algorithm to find a maximum weight max- k -clique subgraph in a cactus subtree graph when k is fixed. In perfect graphs this problem is equivalent to the maximum weight k -colorable subgraph problem. In many applications like scheduling production lines and communication networks on imperfect graphs, a maximum max- k -clique subgraph solution is better than a maximum k -colorable subgraph solution. In addition, we describe cactus subtree graphs polynomial time algorithms for recognition, maximum independent sets, maximum cliques, maximum induced bipartite graphs, maximum induced forests and minimum feedback vertex sets. [ABSTRACT FROM AUTHOR]