Applications of Graph Theory and Logic in Computer Science

Abstract

We study the CSP of unary expansions of directed graphs. When we expand the simple structure (Z,succ) with one unary predicate U , its CSP (Constraint Satisfaction Problem) may vary in complexity. We find some sufficient conditions for its tractability, prove bounds on its complexity, and then generalize our results to more complicated structures. We also give a Karp-equivalent characterization of CSP(Z, succ, U)’s.

Next, fixing α ∈ (0, 1], we generalized the axiomatizations in [1] to the class of hereditarily linearly sparse Kn-free graphs, and made efforts towards connecting this with almost sure theories of Shelah-Spencer graphs, a type of random graphs, which may be of interest in theory of computer science.

Then we study the constraint satisfaction problems of selected infinite relational structures. For α ∈ (0, 5/6], K_α := the class of hereditarily α-sparse graphs, M_α := the generic structure of K_α; K_{α,Kn−free}, M_{α,Kn−free}:= the Kn-free subclass and its generic structure respectively, we prove multiple structural properties of graphs presenting the Hrushovski-Fraïssé class K_{α,TF}, strongly indicating that this class should have a finite homomorphic presentation when α is close to 5/6 from below, which would imply NP-Completeness. More general results are explored along. We also study the complexity-theoretic implications of our findings on a relevant decision problem, namely the constraint satisfaction problem of the corresponding generic structure.