Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2019.tde-08112019-153707
Document
Auteur
Nom complet
Renzo Gonzalo Gómez Diaz
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2019
Directeur
Jury
Wakabayashi, Yoshiko (Président)
Fernandes, Cristina Gomes
Lee, Orlando
Lintzmayer, Carla Negri
Santos, Vinicius Fernandes dos
Titre en anglais
Covering graphs by nontrivial paths
Mots-clés en anglais
Approximation
Bounded treewidth
Covering by nontrivial paths
Integer linear formulation
Max path cover
Min path cover
Weighted path cover
[1,2]-factor
Resumé en anglais
In this thesis our aim is to study problems concerning path covers of graphs. Let G be a graph and let P be a set of pairwise vertex-disjoint paths in G. We say that P is a path cover if every vertex of G belongs to a path in P. In the minimum path cover problem, one wishes to find a path cover of minimum cardinality. In this problem, known to be NP-hard, the set P may contain trivial (single-vertex) paths. We study the problem of finding a path cover composed only of nontrivial paths. First, we consider the corresponding existence problem, and show how to reduce it to a matching problem. From this reduction, we derive a characterization that allows us to find, in polynomial time, a certificate for both the YES-answer and the NO-answer. When trivial paths are forbidden, for the feasible instances, one may consider either minimizing or maximizing the number of paths in the cover. We show that the minimization problem on feasible instances is computationally equivalent to the minimum path cover problem: their optimum values coincide and they have the same approximation threshold. Moreover, we propose integer linear formulations for these problems and present some experimental results. For the maximization problem, we show that it can be solved in polynomial time. Finally, we also consider a weighted version of the path cover problem, in which we seek for a path cover with minimum or maximum total weight (the number of paths does not matter), and we show that while the first is polynomial, the second is NP-hard. Furthermore, for the maximization case, we show a constant-factor approximation algorithm. We also show that, when the input graph has bounded treewidth, both problems can be solved in linear time. To conclude, we present an integer linear formulation for the case of minimum total weight, and study the polytope obtained when the integrality constraint is relaxed. We show that there are graphs for which this polytope has fractional vertices, and we exhibit some classes of inequalities that are valid for the integral polytope and separate these vertices.
Titre en portugais
Cobertura de grafos por caminhos não-triviais
Mots-clés en portugais
Aproximação
Cobertura com pesos
Cobertura máxima
Cobertura mínima
Cobertura por caminhos não-triviais
Formulação linear inteira