LINEAR-TIME OPTIMIZATION ALGORITHMS FOR P-4-SPARSE GRAPHS

Quite often, real-life applications suggest the study of graphs that f eature some local density properties. In particular, graphs that are u nlikely to have more than a few chordless paths of length three appear in a number of contexts. A graph G is P-4-sparse if no set of five ve rtices in G induces more than one chordless path of length three. P-4- sparse graphs generalize both the class of cographs and the class of P -4-reducible graphs. It has been shown that P-4-sparse graphs can be r ecognized in time linear in the size of the graph. The main contributi on of this paper is to show that once the data structures returned by the recognition algorithm are in place, a number of NP-hard problems o n general graphs can be solved in linear time for P-4-sparse graphs. S pecifically with an n-vertex P-4-sparse graph as input the problems of finding a maximum size clique, maximum size stable set, a minimum col oring, a minimum covering by clique, and the size of the minimum fill- in can be solved in O(n) time, independent of the number of edges in t he graph.