The Parameterized Complexity of Learning Monadic Second-Order Logic

HAL (Le Centre pour la Communication Scientifique Directe)

Abstract

Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in monadic second-order logic (MSO). We show that the problem of learning an MSO-definable concept from a training sequence of labeled examples is fixed-parameter tractable on graphs of bounded clique-width, and that it is hard for the parameterized complexity class para-NP on general graphs. It turns out that an important distinction to be made is between 1-dimensional and higher-dimensional concepts, where the instances of a k-dimensional concept are k-tuples of vertices of a graph. For the higher-dimensional case, we give a learning algorithm that is fixed-parameter tractable in the size of the graph, but not in the size of the training sequence, and we give a hardness result showing that this is optimal. By comparison, in the 1-dimensional case, we obtain an algorithm that is fixed-parameter tractable in both.

Authors 3

1. Steffen van Bergerem

   Humboldt-Universität zu Berlin

   Affiliation as printed

   Humboldt-Universität zu Berlin, Germany

2. Martin Grohe Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany

3. Nina Runde Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany