Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

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

ABSTRACT

We study the computational complexity of deciding the existence of a Hamiltonian Cycle in some dense classes of k-uniform hypergraphs. Those problems turned out to be, along with the hypergraph Perfect Matching problems, exceedingly hard, and there is a renewed algorithmic interest in them. In this paper we design a polynomial time algorithm for the Hamiltonian Cycle problem for k-uniform hypergraphs with density at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tfrac12 + \epsilon$\end{document}, ε> 0. In doing so, we depend on a new method of constructing Hamiltonian cycles from (purely) existential statements which could be of independent interest. On the other hand, we establish NP-completeness of that problem for density at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tfrac1k - \epsilon$\end{document}. Our results seem to be the first complexity theoretic results for the Dirac-type dense hypergraph classes. More... »

PAGES

662-673

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-12200-2_57

DOI

http://dx.doi.org/10.1007/978-3-642-12200-2_57

DIMENSIONS

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


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": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We study the computational complexity of deciding the existence of a Hamiltonian Cycle in some dense classes of k-uniform hypergraphs. Those problems turned out to be, along with the hypergraph Perfect Matching problems, exceedingly hard, and there is a renewed algorithmic interest in them. In this paper we design a polynomial time algorithm for the Hamiltonian Cycle problem for k-uniform hypergraphs with density 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}$\\tfrac12 + \\epsilon$\\end{document}, \u03b5>\u20090. In doing so, we depend on a new method of constructing Hamiltonian cycles from (purely) existential statements which could be of independent interest. On the other hand, we establish NP-completeness of that problem for density 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}$\\tfrac1k - \\epsilon$\\end{document}. Our results seem to be the first complexity theoretic results for the Dirac-type dense hypergraph classes.", 
    "editor": [
      {
        "familyName": "L\u00f3pez-Ortiz", 
        "givenName": "Alejandro", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-12200-2_57", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-12199-9", 
        "978-3-642-12200-2"
      ], 
      "name": "LATIN 2010: Theoretical Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "Hamiltonian cycle problem", 
      "computational complexity", 
      "Hamiltonian cycle", 
      "k-uniform hypergraph", 
      "cycle problem", 
      "complexity-theoretic results", 
      "theoretic results", 
      "polynomial time algorithm", 
      "perfect matching problem", 
      "independent interest", 
      "dense class", 
      "NP-completeness", 
      "dense hypergraphs", 
      "time algorithm", 
      "matching problem", 
      "hypergraphs", 
      "problem", 
      "new method", 
      "class", 
      "existential statements", 
      "complexity", 
      "algorithm", 
      "existence", 
      "density", 
      "results", 
      "interest", 
      "statements", 
      "hand", 
      "cycle", 
      "method", 
      "paper"
    ], 
    "name": "Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs", 
    "pagination": "662-673", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011725663"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-12200-2_57"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-12200-2_57", 
      "https://app.dimensions.ai/details/publication/pub.1011725663"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:12", 
    "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_177.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-12200-2_57"
  }
]
 

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-12200-2_57'

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-12200-2_57'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-12200-2_57'

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-12200-2_57'


 

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

107 TRIPLES      22 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-12200-2_57 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc46045700d9e4b8886b420e2f99ddb8a
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We study the computational complexity of deciding the existence of a Hamiltonian Cycle in some dense classes of k-uniform hypergraphs. Those problems turned out to be, along with the hypergraph Perfect Matching problems, exceedingly hard, and there is a renewed algorithmic interest in them. In this paper we design a polynomial time algorithm for the Hamiltonian Cycle problem for k-uniform hypergraphs with density at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tfrac12 + \epsilon$\end{document}, ε> 0. In doing so, we depend on a new method of constructing Hamiltonian cycles from (purely) existential statements which could be of independent interest. On the other hand, we establish NP-completeness of that problem for density at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tfrac1k - \epsilon$\end{document}. Our results seem to be the first complexity theoretic results for the Dirac-type dense hypergraph classes.
7 schema:editor Nff7c7b68914442adadedf53dedd19815
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N37c9a8fa0c45435e962d6940ead9628b
11 schema:keywords Hamiltonian cycle
12 Hamiltonian cycle problem
13 NP-completeness
14 algorithm
15 class
16 complexity
17 complexity-theoretic results
18 computational complexity
19 cycle
20 cycle problem
21 dense class
22 dense hypergraphs
23 density
24 existence
25 existential statements
26 hand
27 hypergraphs
28 independent interest
29 interest
30 k-uniform hypergraph
31 matching problem
32 method
33 new method
34 paper
35 perfect matching problem
36 polynomial time algorithm
37 problem
38 results
39 statements
40 theoretic results
41 time algorithm
42 schema:name Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs
43 schema:pagination 662-673
44 schema:productId N0bc1ca16bf9f408dba1a367982561330
45 N2d2d34d461b14c659dad624cea6b5c19
46 schema:publisher N1a4beca85514447d870608ee149a1680
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011725663
48 https://doi.org/10.1007/978-3-642-12200-2_57
49 schema:sdDatePublished 2022-11-24T21:12
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nf5dc0be346f348d09b354503f6045690
52 schema:url https://doi.org/10.1007/978-3-642-12200-2_57
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N0bc1ca16bf9f408dba1a367982561330 schema:name dimensions_id
57 schema:value pub.1011725663
58 rdf:type schema:PropertyValue
59 N1a4beca85514447d870608ee149a1680 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N2d2d34d461b14c659dad624cea6b5c19 schema:name doi
62 schema:value 10.1007/978-3-642-12200-2_57
63 rdf:type schema:PropertyValue
64 N37c9a8fa0c45435e962d6940ead9628b schema:isbn 978-3-642-12199-9
65 978-3-642-12200-2
66 schema:name LATIN 2010: Theoretical Informatics
67 rdf:type schema:Book
68 N7d22515ab5894c30bc6c4717f2656cf2 rdf:first sg:person.014260054065.30
69 rdf:rest rdf:nil
70 Nab03fefc4e764ed2b194891f9bfd79ed schema:familyName López-Ortiz
71 schema:givenName Alejandro
72 rdf:type schema:Person
73 Nb016a31c5ec248029e87e731cdfdb0da rdf:first sg:person.015322164316.14
74 rdf:rest N7d22515ab5894c30bc6c4717f2656cf2
75 Nc46045700d9e4b8886b420e2f99ddb8a rdf:first sg:person.011636042271.02
76 rdf:rest Nb016a31c5ec248029e87e731cdfdb0da
77 Nf5dc0be346f348d09b354503f6045690 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 Nff7c7b68914442adadedf53dedd19815 rdf:first Nab03fefc4e764ed2b194891f9bfd79ed
80 rdf:rest rdf:nil
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computation Theory and Mathematics
86 rdf:type schema:DefinedTerm
87 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
88 schema:familyName Karpiński
89 schema:givenName Marek
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
91 rdf:type schema:Person
92 sg:person.014260054065.30 schema:affiliation grid-institutes:grid.5633.3
93 schema:familyName Szymańska
94 schema:givenName Edyta
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014260054065.30
96 rdf:type schema:Person
97 sg:person.015322164316.14 schema:affiliation grid-institutes:grid.5633.3
98 schema:familyName Ruciński
99 schema:givenName Andrzej
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015322164316.14
101 rdf:type schema:Person
102 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn
103 schema:name Department of Computer Science, University of Bonn
104 rdf:type schema:Organization
105 grid-institutes:grid.5633.3 schema:alternateName Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań
106 schema:name Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań
107 rdf:type schema:Organization
 




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


...