Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem

2023/07/03 by Argyrios Deligkas, Eduard Eiben, Deligkas, Argyrios +7
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Defense, Military, and Policy Studies #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2307.01109

openalex publication_date 2023/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrary digraphs, on oriented digraphs, and on symmetric digraphs. We demonstrate applications of the dichotomies for binary-action polymatrix games and several graph theory problems.

Related

• Out-degree reducing partitions of digraphs
• The Complexity of Max-Min k-Partitioning
• Digraph Decompositions and Monotonicity in Digraph Searching
• Problems and results on judicious partitions
• Majority out-dominating functions in digraphs