Premium
Multi‐budgeted matching problems
Author(s) -
Büsing Christina,
Comis Martin
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21802
Subject(s) - treewidth , bounded function , matching (statistics) , partial k tree , extension (predicate logic) , reduction (mathematics) , steiner tree problem , mathematics , graph , transformation (genetics) , budget constraint , submodular set function , computer science , mathematical optimization , pathwidth , combinatorics , line graph , statistics , mathematical analysis , biochemistry , geometry , chemistry , neoclassical economics , economics , gene , programming language
The multi‐budgeted matching problem (mBM) is a weighted matching problem with k independent edge cost functions. For each cost function, a budget constraint requires the accumulated cost not to exceed a corresponding budget. We show that the mBM is strongly NP‐hard on paths with uniform edge weights and budgets by a reduction from 3‐SAT. Subsequently, we propose a dynamic program for series‐parallel graphs with pseudo‐polynomial run time for a fixed number of budget constraints. As an extension we show how this algorithm can be used to solve the mBM on trees using a graph transformation. Realizing that both these graph classes have a bounded treewidth in common, we introduce a dynamic program based on tree decompositions. This approach leads to a pseudo‐polynomial algorithm for the mBM with fixed k on graphs of bounded treewidth.