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 (Corresponding author)

Graph Algorithms

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

1 Downloads (Pure)

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	Graphs and Combinatorial Optimization: from Theory to Applications
Subtitle of host publication	CTW 2023, Garmisch-Partenkirchen, Germany, June 20–22
Editors	Andreas Brieden, Stefan Pickl, Markus Siegle
Publisher	Springer Nature
Chapter	1
Pages	1-13
Number of pages	13
ISBN (Electronic)	978-3-031-46826-1
ISBN (Print)	978-3-031-46825-4
DOIs	https://doi.org/10.1007/978-3-031-46826-1_1
Publication status	Published - Feb 2024
Event	CTW2023: 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization - Garmisch-Partenkirchen, Germany Duration: 20 Jun 2023 → 22 Jun 2023

Publication series

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

Conference

Conference	CTW2023: 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Abbreviated title	CTW2023
Country/Territory	Germany
City	Garmisch-Partenkirchen
Period	20/06/23 → 22/06/23

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

@inproceedings{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.; CTW2023: 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW2023 ; Conference date: 20-06-2023 Through 22-06-2023",

year = "2024",

month = feb,

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

language = "English",

isbn = "978-3-031-46825-4",

series = "AIRO Springer Series",

publisher = "Springer Nature",

pages = "1--13",

editor = "Andreas Brieden and Stefan Pickl and Markus Siegle",

booktitle = "Graphs and Combinatorial Optimization: from Theory to Applications",

address = "Singapore",

}

Verhaegh, RFA 2024, The Algorithmic Complexity of the Paired Matching Problem. in A Brieden, S Pickl & M Siegle (eds), Graphs and Combinatorial Optimization: from Theory to Applications: CTW 2023, Garmisch-Partenkirchen, Germany, June 20–22. AIRO Springer Series, vol. 13, Springer Nature, pp. 1-13, CTW2023: 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Garmisch-Partenkirchen, Germany, 20/06/23. https://doi.org/10.1007/978-3-031-46826-1_1

The Algorithmic Complexity of the Paired Matching Problem. / Verhaegh, Ruben F.A. (Corresponding author).
Graphs and Combinatorial Optimization: from Theory to Applications: CTW 2023, Garmisch-Partenkirchen, Germany, June 20–22. ed. / Andreas Brieden; Stefan Pickl; Markus Siegle. Springer Nature, 2024. p. 1-13 (AIRO Springer Series; Vol. 13).

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

TY - GEN

T1 - The Algorithmic Complexity of the Paired Matching Problem

AU - Verhaegh, Ruben F.A.

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

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 - https://www.scopus.com/pages/publications/85186442990

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

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

M3 - Conference contribution

AN - SCOPUS:85186442990

SN - 978-3-031-46825-4

T3 - AIRO Springer Series

SP - 1

EP - 13

BT - Graphs and Combinatorial Optimization: from Theory to Applications

A2 - Brieden, Andreas

A2 - Pickl, Stefan

A2 - Siegle, Markus

PB - Springer Nature

T2 - CTW2023: 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization

Y2 - 20 June 2023 through 22 June 2023

ER -