Search

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. Ordered pathwidth is roughly the same as proof space and the ordered treewidth of a proof is meant to serve as a measure of how far it is from being treelike. Length-space lower bounds for k -DNF refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth. [ABSTRACT FROM AUTHOR]

Abstract: We prove that if a tournament has pathwidth then it has θ vertices that are pairwise θ-connected. As a consequence of this and previous results, we obtain that for every set of tournaments the following are equivalent: [•] there exists k such that every member of has pathwidth at most k, [•] there is a digraph H such that no subdivision of H is a subdigraph of any member of , [•] there exists k such that for each , there do not exist k vertices of T that are pairwise k-connected. As a further consequence, we obtain a polynomial-time algorithm to test whether a tournament contains a subdivision of a fixed digraph H as a subdigraph. [Copyright &y& Elsevier]