Parameterized Complexity of Spanning Tree Problems with Local Constraints.

EasyChair Preprint 2648

Abstract

We introduce in this presentation the minimum subTree with Local Weights problem (MTLW) which generalizes the search of a subtree in a graph that must satisfy m constraints and minimize an objective function. The m constraints and the objective functions are defined as functions with a node and a subset of incident edges as input and returning a (positive or negative) integer as output, we assume those functions are computable in polynomial time.

Given a subtree of the graph, we compute, for each function, the sum for each node of the graph and each set of incident edges in the tree of the values of that function. This gives m + 1 integers. The problem consists in the search for a subtree minimizing the last value and such that the m first values are lower than m integers given as  input. This problem is a generalization of many spanning and covering tree problems that can be found in the litterature.

A natural question to ask is whether all those problems are simpler when the graph is close to a tree or not. A classical way to measure that is to use the treewidth of the graph. It was proved that the Steiner Tree problem and the k-Spanning tree problems are FPT with respect to the treewidth. We investigate here if this is the case for MTLW. We also look at the cyclomatique number which is another parameter that define distance between a graph and a tree.

In this presentation, we show parameterized complexity restults with respect to those two parameters for MTLW. Particularly, we show that MTLW is not FPT with any parameter but, by restricting the instances of MTLW, it is possible to find an FPT algorithm with respect to the treewidth and the cyclomatic number, and this algorithm demonstrate the fixed-parameterized tracatbility of many problems that can be found in the litterature.

Keyphrases: Arbre couvrant, Complexité paramétrée, Largeur d’arbre, Nombre cyclomatique

@booklet{EasyChair:2648,
  author    = {Dimitri Watel and Massinissa Merabet},
  title     = {Parameterized Complexity of Spanning Tree Problems with Local Constraints.},
  howpublished = {EasyChair Preprint 2648},
  year      = {EasyChair, 2020}}