Mitarbeiterseminar Logik in der Informatik

We study the definability of finite graphs in first order logic with two relation symbols for adjacency and equality of vertices. The logical depth D(G) of a graph G is equal to the minimum quantifier depth of a sentence defining G up to isomorphism. The logical width W(G) is the minimum number of variables occurring in such a sentence. We overview known estimates for these graph parameters and discuss their relations to other research areas.

The Min Ones Constraint Satisfaction Problems unify problems like Vertex Cover, Hitting Set and Nearest Codeword, allowing them to be studied in one framework. An instance (F,k) of Min Ones CSP(Gamma) consists of a formula F, given as a conjunction of constraints, and a number k, and the question is whether F has a satisfying assignment with at most k true variables. The constraint types are taken from a fixed, finite set Gamma of boolean relations, and the complexity of the problem depends on the set Gamma. For example, if Gamma={(x or y)}, then we get the problem Vertex Cover, while another Gamma gives us the more expressive Min Ones 3-SAT problem.

Starting from the well-known kernelizable cases of d-Hitting Set, it is natural to ask whether the problem always admits polynomial kernelizations. As we show, this is not the case. We give a property we refer to as mergeability, and show that if every relation in Gamma is mergeable, then the problem has a kernel of O(k^(d+1)) vertices, where d is the maximum arity of a relation in Gamma. On the other hand, if Gamma contains at least one relation which is not mergeable, then we use the framework of Fortnow and Santhanam, and Bodlaender et al., to show that the problem admits no polynomial kernelization unless the polynomial hierarchy collapses (excepting the cases of Min Ones CSP(Gamma) which are completely solvable in polynomial time).

We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above tight lower bound, which is stated as follows. For a set V of variables and set C of constraints "u is between v and w", decide whether there is a bijection from V to the set {1,...,|V|} satisfying at least |C|/3 + k of the constraints in C. Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph "Invitation to Fixed-Parameter Algorithms".

Interval graphs are the intersection graphs of intervals on the reals. In this talk, I will outline my proof that fixed-point logic with counting (FP+C) captures polynomial-time on the class of all finite interval graphs. As will be shown, any interval graph possesses structural properties that allow to construct in FP+C a canonical copy of the graph with linearly ordered vertices. By the Immerman-Vardi Theorem, all PTIME properties can then be defined by a fixed-point formula on this ordered copy. The result is part of a wider project to determine capturing results for graph classes defined by forbidden induced subgraphs.