Path-closed sets (Q802569): Difference between revisions

A subset T of the node set V of a digraph \(G=(V,E)\) is called path-closed if for each v,v'\(\in T\) all nodes lying on directed paths from v to v' also belong to T. The author characterizes the convex hull of the incidence vectors of all path-closed sets by a set of linear inequalities thus turning the problem of finding a maximum path-closed set (in a graph with weighted vertices) into an LP, and he gives a fast algorithm for solving it. Some other results like a min-max-theorem on partitioning a given subset of V into a minimum number of path-closed sets and an analogue to Dilworth's theorem are also derived.