Sentiment analysis (SA) on Vietnamese is challenging because of the complexity of the language and its reliance on tonal nuances and context-aware structures. Graph Neural Networks (GNNs) have shown superior performance on SA tasks using graph representations of text. Nevertheless, the dense graph structures commonly used in GNN models result in excessive computation overhead with little gain in terms of performance. In this paper, we propose a novel method to combine dependency parsing (DP) to reduce graph construction overhead in GNN-based Vietnamese SA. We leverage DP to selectively prune syntactic dependencies to compress the graph and eliminate redundant edges while keeping syntactic and semantic relations intact. Experiments on a range of Vietnamese SA datasets show that the proposed technique substantially lowers computation overhead while providing comparable or better performance compared to baseline GNN models with full-graph structures. This work shows the promise of using DP-assisted GNN as a low-overhead but efficient solution to Vietnamese SA and opens up the scope of applying it to other linguistically complex and low-resource languages.