# GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning

arXiv: https://arxiv.org/abs/2605.06671 · HTML: https://mlsanity.com/paper/2605.06671/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 13 of its 46 references that are in the map.
- First posted on arXiv 18 Apr 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 13 of 13)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [KICGPT: Large Language Model with Knowledge in Context for Knowledge Graph Completion](https://mlsanity.com/paper/2402.02389/) (2024)
- [Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents](https://mlsanity.com/paper/2410.05130/) (2024)
- [A Survey of Shortest-Path Algorithms](https://mlsanity.com/paper/1705.02044/) (2017)
- [PhysicsAgentABM: Physics-Guided Generative Agent-Based Modeling](https://mlsanity.com/paper/2602.06030/) (2026)
- [Improving Hospital Risk Prediction with Knowledge-Augmented Multimodal EHR Modeling](https://mlsanity.com/paper/2508.01970/) (2025)
- [Learning on Graphs for Mineral Asset Valuation Under Supply and Demand Uncertainty](https://mlsanity.com/paper/2212.03865/) (2022)

## Built on by (most cited first, 1 of 1)

- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have demonstrated strong potential for many mathematical problems. However, their performance on graph algorithmic tasks is still unsatisfying, since graphs are naturally more complex in topology and often require systematic multi-step reasoning, especially on larger graphs. Motivated by this gap, we propose GraphDC, a Divide-and-Conquer multi-agent framework for scalable graph algorithm reasoning. Specifically, inspired by Divide-and-Conquer design, GraphDC decomposes an input graph into smaller subgraphs, assigns each subgraph to a specialized agent for local reasoning, and uses a master agent to integrate the local outputs with inter-subgraph information to produce the final solution. This hierarchical design reduces the reasoning burden on individual agents, alleviates computational bottlenecks, and improves robustness on large graph instances. Extensive experiments show that GraphDC consistently outperforms existing methods on graph algorithm reasoning across diverse tasks and scales, especially on larger instances where direct end-to-end reasoning is less reliable.