On the rank of Directed Hamiltonicity and beyond

Abstract

Motivated by recent research making use of insights on the relationship between the optimal substructure of dynamic programming procedures and the rank of problem-specific matrices, we investigate the application of this approach in the context of Hamiltonicity. In particular, after briefly introducing the setting, we determine the rank of the Directed Matching Connectivity matrix Dt that has rows/columns indexed by all perfect matchings on the complete digraph on t vertices, while an entry Dt [M1, M2] is 1, if M1 ∪ M2 is a directed Hamiltonian cycle and 0 otherwise. We then provide a Monte Carlo algorithm that uses the row basis Xt for Dt to solve the Directed Hamiltonian Cycle problem on a given path decomposition of width pw in time (2+2^3/2)^pw(pw·n)^O(1) via dynamic programming. Subsequently, we study a generalized setting that considers partitions of elements into blocks of size k instead of perfect matchings only. After expanding the definitions of required concepts, we show how to construct sets of partitions Xt,k that generalize Xt for higher values of k and use them to obtain a non-trivial lower bound on the rank of the Partition Connectivity matrix Ct,k, that itself extends previously considered matrices.