Aspectos computacionais teóricos na convexidade P3: número de Carathéodory e seleção de conjunto alvo

Abstract

The spread of influence in social networks, epidemics, and information diffusion is modeled across several fields. In Graph Theory, convexity provides an elegant formal framework for characterizing propagation processes. A central parameter in this context is the Carathéodory number associated with P3-convexity (paths of three vertices), which measures the maximum size of subsets required to explain the inclusion of vertices in convex hulls. Deciding whether a graph admits a Carathéodory set of cardinality k is NP-complete; however, relevant results can be obtained for specific graph classes. This thesis, organized in the Scandinavian format, presents original results on the Carathéodory number in P3-convexity. We investigate graphs of diameter two, establishing upper bounds for different subclasses.We propose a polynomial-time algorithm that constructs special paths providing computable estimates and a tight upper bound, contributing to the conjecture that the Carathéodory number is bounded by a constant in diameter-two graphs. We analyze circulant graphs, determining exact values for particular cases and lower bounds in general. For Hamming graphs of dimension n, we prove that the Carathéodory number is at least n, highlighting the relationship between dimensionality and convexity parameters. In addition to theoretical results, we address the target set selection problem, a classical model of influence diffusion. We present efficient heuristics that outperform related approaches, validated experimentally on large-scale real social networks and randomly generated instances. Finally, we state conjectures that outline promising research directions, strengthening the connections between graph convexity, computational complexity, and diffusion models in networks.