O posto de Uma Convexidade de Grafos
Autores
|
5594 |
Igor da Fonseca Ramos
|
2573,6,2425
|
|
5595 |
2573,6,2425
|
|
|
5596 |
Vinícius Fernandes dos Santos
(Co-orientador) |
2573,6,2425
|
Informações:
Publicações do PESC
Considerando-se as convexidades de grafos baseadas em caminhos mais estudadas — geodética, monofônica e P3 — a envoltória convexa de um conjunto de vértices S é o menor conjunto convexo do grafo que contém S, representada por H(S). Um conjunto de vértices S é dito convexamente independente se v não pertence a H(S \\\\\\\\ {v}) para todo v pertencente a S. O posto rk(G) de um grafo é a cardinalidade de um conjunto convexamente independente máximo.
Esse trabalho apresenta um estudo sobre a complexidade de tempo do cálculo de rk(G). Prova-se a NP-completude do problema para grafos split e bipartidos na convexidade P3, bem como para grafos sem clique separadora na convexidade monofônica. Já no caso de árvores nas convexidade geodéica, monofônica e P3, bem como de grafos threshold e de intervalo biconexos na convexidade P3, são apresentados algoritmos polinomiais. Finalmente, prova-se, ainda, um limite superior justo para rk(G) na convexidade P3 que, por sua vez, torna possível provar de forma mais simples o limite justo para o número de Radon provado por Henning, Rautenbach e Schäfer.
We consider the most common graph convexities based on paths of vertices — geodetic, monophonic and P3. The convex hull of a set of vertices S is the smallest convex set that contains S and is denoted by H(S). A set of vertices is said to be convexly independent if v is not in H(S \\\\\\\\ {v}) for all v in S. The rank rk(G) of a graph is the cardinality of a maximum convexly independent set.
This text presents a study about the time complexity of determining rk(G). We prove the NP-completeness of the problem for split and bipartite graphs in the context of the P3-convexity. On the other hand, for trees the problem can be solved in polynomial time under the three convexities and we also show that the rank of a threshold or biconnected interval graph can be determined in polynomial time under the P3-convexity. Finally, we prove a tight upper bound for rk(G) in the P3-convexity that, in turn, provides a simpler proof to the already known upper bound for the Radon number given by Henning, Rautenbach and Schäfer.