{"id":"arxiv/2608.18514","url":"https://arxiv.org/abs/2608.18514","tags":["cs.LO","cs.DM","math.CO"],"score":0,"title":"Exact SAT Solving for the Two-Dimensional Bandwidth Minimization Problem","domain":"cs.LO","source":"arxiv","authors":["Pham Quang Minh","Dao Xuan Nghia","To Van Khanh"],"reviews":0,"subject":"cs.LO","summary":"The two-dimensional bandwidth minimization problem (2DBMP) seeks an injective embedding of a guest graph into a square grid that minimizes the maximum Manhattan distance over its edges. Heuristic methods can provide strong upper bounds, but these bounds do not by themselves certify optimality. We present an efficient exact SAT-based approach for 2DBMP that incrementally searches for the minimum feasible bandwidth and certifies optimality through satisfiability and unsatisfiability results. On the standard $\\lceil\\sqrt n\\rceil \\times \\lceil\\sqrt n\\rceil$ host grid, under a 3600 s time limit,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}