The Complexity of Perfect Matching Problems on Dense Hypergraphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Marek Karpiński , Andrzej Ruciński , Edyta Szymańska

ABSTRACT

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. Some of these problems are known to be notoriously hard. There is also a renewed interest recently in the very special cases of them. One of the goals of this paper is to shed some light on the tractability barriers for those problems.It has been known that the perfect matching problems are NP-complete for the classes of hypergraphs H with minimum ((k − 1) −wise) vertex degreeδ at least c|V(H)| for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c<\frac 1k$\end{document} and trivial for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c\ge\frac 12,$\end{document} leaving the status of the problems with c in the interval \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$[\frac 1k,\frac 12)$\end{document} widely open. In this paper we show, somehow surprisingly, that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac 12$\end{document}, in fact, is not a threshold for the tractability of the perfect matching problem, and prove the existence of an ε> 0 such that the perfect matching problem for the class of hypergraphs H with δ at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac 12-\epsilon)|V(H)|$\end{document} is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest in view of the known results for graphs. More... »

PAGES

626-636

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_64

DOI

http://dx.doi.org/10.1007/978-3-642-10631-6_64

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1017585919


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpi\u0144ski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144", 
          "id": "http://www.grid.ac/institutes/grid.5633.3", 
          "name": [
            "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ruci\u0144ski", 
        "givenName": "Andrzej", 
        "id": "sg:person.015322164316.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015322164316.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144", 
          "id": "http://www.grid.ac/institutes/grid.5633.3", 
          "name": [
            "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szyma\u0144ska", 
        "givenName": "Edyta", 
        "id": "sg:person.014260054065.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014260054065.30"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. Some of these problems are known to be notoriously hard. There is also a renewed interest recently in the very special cases of them. One of the goals of this paper is to shed some light on the tractability barriers for those problems.It has been known that the perfect matching problems are NP-complete for the classes of hypergraphs H with minimum ((k\u2009\u2212\u20091)\u2009\u2212wise) vertex degree\u03b4 at least c|V(H)| for \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$c<\\frac 1k$\\end{document} and trivial for \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$c\\ge\\frac 12,$\\end{document} leaving the status of the problems with c in the interval \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$[\\frac 1k,\\frac 12)$\\end{document} widely open. In this paper we show, somehow surprisingly, that \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\frac 12$\\end{document}, in fact, is not a threshold for the tractability of the perfect matching problem, and prove the existence of an \u03b5>\u20090 such that the perfect matching problem for the class of hypergraphs H with \u03b4 at least \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$(\\frac 12-\\epsilon)|V(H)|$\\end{document} is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest in view of the known results for graphs.", 
    "editor": [
      {
        "familyName": "Dong", 
        "givenName": "Yingfei", 
        "type": "Person"
      }, 
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-10631-6_64", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-10630-9", 
        "978-3-642-10631-6"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "perfect matching problem", 
      "matching problem", 
      "first polynomial-time algorithm", 
      "polynomial time algorithm", 
      "existence problem", 
      "certain class", 
      "parallel complexity", 
      "computational complexity", 
      "special case", 
      "independent interest", 
      "k-uniform hypergraph", 
      "hypergraph H", 
      "polynomial time", 
      "dense hypergraphs", 
      "perfect matching", 
      "time algorithm", 
      "hypergraphs", 
      "problem", 
      "complexity", 
      "class", 
      "existence", 
      "tractability", 
      "graph", 
      "algorithm", 
      "NPs", 
      "matching", 
      "interest", 
      "cases", 
      "fact", 
      "results", 
      "interval", 
      "threshold", 
      "time", 
      "goal", 
      "view", 
      "addition", 
      "light", 
      "barriers", 
      "status", 
      "paper"
    ], 
    "name": "The Complexity of Perfect Matching Problems on Dense Hypergraphs", 
    "pagination": "626-636", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017585919"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-10631-6_64"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-10631-6_64", 
      "https://app.dimensions.ai/details/publication/pub.1017585919"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_30.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-10631-6_64"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_64'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_64'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_64'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_64'


 

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      22 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-10631-6_64 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5257160b46ac40b8a42d64ecfd58d574
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. Some of these problems are known to be notoriously hard. There is also a renewed interest recently in the very special cases of them. One of the goals of this paper is to shed some light on the tractability barriers for those problems.It has been known that the perfect matching problems are NP-complete for the classes of hypergraphs H with minimum ((k − 1) −wise) vertex degreeδ at least c|V(H)| for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c<\frac 1k$\end{document} and trivial for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c\ge\frac 12,$\end{document} leaving the status of the problems with c in the interval \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$[\frac 1k,\frac 12)$\end{document} widely open. In this paper we show, somehow surprisingly, that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac 12$\end{document}, in fact, is not a threshold for the tractability of the perfect matching problem, and prove the existence of an ε> 0 such that the perfect matching problem for the class of hypergraphs H with δ at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac 12-\epsilon)|V(H)|$\end{document} is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest in view of the known results for graphs.
7 schema:editor Nf699b2f25f02416cb8a688c50373f06b
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N61c38f4e7d054acd868d5134746770b5
11 schema:keywords NPs
12 addition
13 algorithm
14 barriers
15 cases
16 certain class
17 class
18 complexity
19 computational complexity
20 dense hypergraphs
21 existence
22 existence problem
23 fact
24 first polynomial-time algorithm
25 goal
26 graph
27 hypergraph H
28 hypergraphs
29 independent interest
30 interest
31 interval
32 k-uniform hypergraph
33 light
34 matching
35 matching problem
36 paper
37 parallel complexity
38 perfect matching
39 perfect matching problem
40 polynomial time
41 polynomial time algorithm
42 problem
43 results
44 special case
45 status
46 threshold
47 time
48 time algorithm
49 tractability
50 view
51 schema:name The Complexity of Perfect Matching Problems on Dense Hypergraphs
52 schema:pagination 626-636
53 schema:productId N17fe004420bd4bc79d313f578e373596
54 Na7ffae1ae0a54ef588158c563317a038
55 schema:publisher N0dc1258d46394b35b14c4b1fcb0059a7
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017585919
57 https://doi.org/10.1007/978-3-642-10631-6_64
58 schema:sdDatePublished 2022-11-24T21:15
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N0af7aed600c24d1497a71df8a8cbffab
61 schema:url https://doi.org/10.1007/978-3-642-10631-6_64
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N0af7aed600c24d1497a71df8a8cbffab schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N0dc1258d46394b35b14c4b1fcb0059a7 schema:name Springer Nature
68 rdf:type schema:Organisation
69 N17c14a5292ae44daa780b5e50c8d9d7f schema:familyName Dong
70 schema:givenName Yingfei
71 rdf:type schema:Person
72 N17fe004420bd4bc79d313f578e373596 schema:name doi
73 schema:value 10.1007/978-3-642-10631-6_64
74 rdf:type schema:PropertyValue
75 N5257160b46ac40b8a42d64ecfd58d574 rdf:first sg:person.011636042271.02
76 rdf:rest N64f4dfb06dcd46faac8329f4f9d98311
77 N548bc86c71914f80821d9d420a61fbf8 schema:familyName Ibarra
78 schema:givenName Oscar
79 rdf:type schema:Person
80 N61c38f4e7d054acd868d5134746770b5 schema:isbn 978-3-642-10630-9
81 978-3-642-10631-6
82 schema:name Algorithms and Computation
83 rdf:type schema:Book
84 N64f4dfb06dcd46faac8329f4f9d98311 rdf:first sg:person.015322164316.14
85 rdf:rest Ncad93fb76db542079a2a7fe350c812a1
86 N7045f7ac9a3b4bab996399c09313fa8a schema:familyName Du
87 schema:givenName Ding-Zhu
88 rdf:type schema:Person
89 Na7ffae1ae0a54ef588158c563317a038 schema:name dimensions_id
90 schema:value pub.1017585919
91 rdf:type schema:PropertyValue
92 Ncad93fb76db542079a2a7fe350c812a1 rdf:first sg:person.014260054065.30
93 rdf:rest rdf:nil
94 Ncd8421229d7c407997cae574d5972b8a rdf:first N7045f7ac9a3b4bab996399c09313fa8a
95 rdf:rest Nfcfaaccb31c54b43828020f6f38abe08
96 Nf699b2f25f02416cb8a688c50373f06b rdf:first N17c14a5292ae44daa780b5e50c8d9d7f
97 rdf:rest Ncd8421229d7c407997cae574d5972b8a
98 Nfcfaaccb31c54b43828020f6f38abe08 rdf:first N548bc86c71914f80821d9d420a61fbf8
99 rdf:rest rdf:nil
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
104 schema:name Computation Theory and Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
107 schema:familyName Karpiński
108 schema:givenName Marek
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
110 rdf:type schema:Person
111 sg:person.014260054065.30 schema:affiliation grid-institutes:grid.5633.3
112 schema:familyName Szymańska
113 schema:givenName Edyta
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014260054065.30
115 rdf:type schema:Person
116 sg:person.015322164316.14 schema:affiliation grid-institutes:grid.5633.3
117 schema:familyName Ruciński
118 schema:givenName Andrzej
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015322164316.14
120 rdf:type schema:Person
121 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn
122 schema:name Department of Computer Science, University of Bonn
123 rdf:type schema:Organization
124 grid-institutes:grid.5633.3 schema:alternateName Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań
125 schema:name Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań
126 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...