Problemas de partição de caminhos em digrafos

Orientador: Orlando Lee Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Seja D um digrafo. Um subconjunto S de V(D) é um conjunto estável se todo par de vértices em S é não adjacente em D. Uma coleção de caminhos disjuntos P de D é uma partição de caminhos de D, se todo vértice em V(D) pertence a exatamente um caminho de P. Dizemos que um conjunto estável S e uma partição de caminhos P são ortogonais se todo caminho de P contém exatamente um vértice de S. Um digrafo D satisfaz a alpha-propriedade se para todo conjunto estável máximo S de D existe uma partição de caminhos P tal que S e P são ortogonais. Um digrafo D é alpha-diperfeito se todo subdigrafo induzido de D satisfaz a alpha-propriedade. Em 1982, Berge propôs uma caracterização para digrafos alpha-diperfeitos em termos da proibição de circuitos ímpares anti-orientados induzidos. Em 2018, Sambinelli, Silva e Lee propuseram uma conjectura semelhante. Um digrafo D satisfaz a Begin-End-propriedade, ou BE-propriedade, se para todo conjunto estável máximo S de D, existe uma partição de caminhos P tal que (i) S e P são ortogonais e (ii) para todo caminho P em P, o início ou o fim de P pertence a S. Um digrafo D é BE-diperfeito se todo subdigrafo induzido de D satisfaz a BE-propriedade. Sambinelli, Silva e Lee propuseram uma caracterização para digrafos BE-diperfeitos em termos da proibição de circuitos ímpares bloqueantes induzidos. Nesta tese, verificamos ambas as conjecturas para digrafos arco-local in-semicompletos, arco-local out-semicompletos, arco-local semicompletos, 3-anti-circulantes, 3-anti-digon-circulantes e quase-transitivos. Além disso, provamos alguns resultados parciais para digrafos 3-quase-transitivos, 4-transitivos, k-semi-simétricos e digrafos com número de estabilidade igual a dois. Também demonstramos alguns resultados estruturais para digrafos alpha-diperfeitos e BE-diperfeitos. Além disso, fornecemos uma decomposição para digrafos arbitrários arco-local (out) in-semicompletos e para arbitrários arco-local semicompletos. Mostramos que a estrutura desses digrafos é semelhante a digrafos diperfeitos. Ademais, fornecemos alguns resultados estruturais para digrafos 3-anti-digon-circulantes. Demonstramos que a estrutura desses digrafos é semelhante a digrafos completos e bipartidos completos Abstract: Let D be a digraph. A subset S of V(D) is a stable set if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths P of D is a path partition of D, if every vertex in V(D) belongs to exactly one path of P. We say that a stable set S and a path partition P are orthogonal if every path of P contains exactly one vertex of S. A digraph D satisfies the alpha-property if for every maximum stable set S of D, there exists a path partition P such that S and P are orthogonal. A digraph D is alpha-diperfect if every induced subdigraph of D satisfies the alpha-property. In 1982, Berge proposed a characterization for alpha-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture concerning BE-diperfect digraphs. A digraph D satisfies the Begin-End-property, or BE-property, if for every maximum stable set S of D, there exists a path partition P such that (i) S and P are orthogonal and (ii) for every path P in P, either the initial vertex or the terminal vertex of P lies in S. A digraph D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization for BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this text, we verify both conjectures for arc-locally in-semicomplete digraphs, arc-locally out-semicomplete digraphs, arc-locally semicomplete digraphs, 3-anti-circulant digraphs, 3-anti-digon-circulant digraphs and quasi-transitive digraphs. Also, we show some partial results for 3-quasi-transitive digraphs, 4-transitive digraphs, k-semi-symmetric digraphs and digraphs with stability number two. We also prove some structural results for alpha-diperfect and BE-diperfect digraphs. Furthermore, we provide a decomposition for arbitrary arc-locally (out) in-semicomplete digraphs and for arbitrary arc-locally semicomplete digraphs. We show that the structure of these digraphs is very similar to diperfect digraphs. Moreover, we provide some structural results for 3-anti-digon-circulant digraphs. We show that the structure these digraphs is very close to complete and complete bipartite digraphs Doutorado Ciência da Computação Doutor em Ciência da Computação