The Algorithmic Complexity of the Paired Matching Problem

Ruben F.A. Verhaegh

doi:10.1007/978-3-031-46826-1_1

The Algorithmic Complexity of the Paired Matching Problem

Ruben F.A. Verhaegh

Graph Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum matching of minimum cost in a bipartite graph. This is complicated by a non-trivial definition of cost, which is expressed based on a pairing of the vertices in one partite set. We prove that the problem is NP-complete even under further restrictions. We also study the parameterized complexity of the problem and give an exact algorithm for it using kernelization. In doing so, we show that the problem can be solved efficiently even on large inputs, as long as a given one of the partite sets is small.

Original language	English
Title of host publication	19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW2023
Publisher	Springer Nature
Pages	1-13
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-031-46826-1_1
Publication status	Published - Feb 2024

Publication series

Name	AIRO Springer Series
Volume	13
ISSN (Print)	2523-7047
ISSN (Electronic)	2523-7055

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Access to Document

10.1007/978-3-031-46826-1_1

Cite this

@inbook{ffcb8bbc5edc4011a1579d6ff64e85e9,

title = "The Algorithmic Complexity of the Paired Matching Problem",

abstract = "We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum matching of minimum cost in a bipartite graph. This is complicated by a non-trivial definition of cost, which is expressed based on a pairing of the vertices in one partite set. We prove that the problem is NP-complete even under further restrictions. We also study the parameterized complexity of the problem and give an exact algorithm for it using kernelization. In doing so, we show that the problem can be solved efficiently even on large inputs, as long as a given one of the partite sets is small.",

author = "Verhaegh, {Ruben F.A.}",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.",

year = "2024",

month = feb,

doi = "10.1007/978-3-031-46826-1_1",

language = "English",

series = "AIRO Springer Series",

publisher = "Springer Nature",

pages = "1--13",

booktitle = "19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW2023",

address = "Singapore",

}

TY - CHAP

T1 - The Algorithmic Complexity of the Paired Matching Problem

AU - Verhaegh, Ruben F.A.

PY - 2024/2

Y1 - 2024/2

N2 - We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum matching of minimum cost in a bipartite graph. This is complicated by a non-trivial definition of cost, which is expressed based on a pairing of the vertices in one partite set. We prove that the problem is NP-complete even under further restrictions. We also study the parameterized complexity of the problem and give an exact algorithm for it using kernelization. In doing so, we show that the problem can be solved efficiently even on large inputs, as long as a given one of the partite sets is small.

AB - We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum matching of minimum cost in a bipartite graph. This is complicated by a non-trivial definition of cost, which is expressed based on a pairing of the vertices in one partite set. We prove that the problem is NP-complete even under further restrictions. We also study the parameterized complexity of the problem and give an exact algorithm for it using kernelization. In doing so, we show that the problem can be solved efficiently even on large inputs, as long as a given one of the partite sets is small.

UR - http://www.scopus.com/inward/record.url?scp=85186442990&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-46826-1_1

DO - 10.1007/978-3-031-46826-1_1

M3 - Chapter

AN - SCOPUS:85186442990

T3 - AIRO Springer Series

SP - 1

EP - 13

BT - 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW2023

PB - Springer Nature

ER -