Finding a maximum-weight induced k k -partite subgraph of an i i -triangulated graph
An i i -triangulated graph  is a graph in which every odd cycle has two non-crossing chords; i i -triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable  graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k k -partite subgraph of an i i -triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP -complete.
clique-separable graph graph algorithm i i -triangulated graph i i i i i tree decomposition