License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.29
URN: urn:nbn:de:0030-drops-68642
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6864/
Go to the corresponding LIPIcs Volume Portal

Gupta, Sushmita ; Roy, Sanjukta

Stable Matching Games: Manipulation via Subgraph Isomorphism

pdf-format:
LIPIcs-FSTTCS-2016-29.pdf (0.5 MB)

Abstract

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the Stable Extension of Partial Matching (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui [Algorithmica, 2010] proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2^{O(n)}, where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2^{o(n)}. Our algorithm is a non-trivial combination of a parameterized algorithm for Subgraph Isomorphism, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating non-isomorphic out-branchings.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2016:6864,
  author =	{Sushmita Gupta and Sanjukta Roy},
  title =	{{Stable Matching Games: Manipulation via Subgraph Isomorphism}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6864},
  URN =		{urn:nbn:de:0030-drops-68642},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.29},
  annote =	{Keywords: stable matching, Gale-Shapley algorithm, suitor graph, subgraph iso- morphism, exact-exponential time algorithms}
}

Keywords: stable matching, Gale-Shapley algorithm, suitor graph, subgraph iso- morphism, exact-exponential time algorithms
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI