The multi-terminal vertex separator problem: total dual integrality and polytope composition

Let $$G=(V\cup T,E)$$ be a graph where $$V\cup T$$ is the set of vertices, with T a subset of distinguished vertices, called terminals, and E the set of edges. Given a weight function $$w: V\rightarrow \mathbb N{\setminus } \{0\}$$ associated with the nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning $$V\cup T$$ into $$k+1$$ subsets $$\{S, V_1,\dots , V_k\}$$ such that there is no edge between two different subsets $$V_i$$ and $$V_j$$ , each $$V_i$$ contains exactly one terminal and the weight of S is minimum. In this paper, we characterize the polytope of the solutions of this problem for two classes of the graph, and we show that the two linear systems are totally dual integral. Then, we study the polytope for the graphs that are decomposable by 1-node cutsets. We show that if G decomposes into $$G_1, \dots , G_k$$ , then the polytope in G can be obtained from those in $${\bar{G}}_1, \dots , {\bar{G}}_k$$ , where $${\bar{G}}_1, \dots , {\bar{G}}_k$$ are graphs related to $$G_1, \dots , G_k$$ , respectively. We also derive a procedure for composing facets and give some algorithmic consequences for solving the problem in G from $${\bar{G}}_1, \dots , {\bar{G}}_k$$ .