We present a formalization of dependency labeling with Integer Linear Programming. We focus on the integration of subcategorization into the decision making process, where the various subcategorization frames of a verb compete with each other. A maximum entropy model provides the weights for ILP optimization. tion. More formally, the dependency labeling problem is: given a sentence with (i) verbs, , (ii) NP 1, and PP chunks , label all pairs ( ) with a dependency relation (including a class for the null assignment) such that all chunks get attached and for each verb exactly one subcategorization frame is instantiated