The Kr-Packing Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-03

AUTHORS

Venkatesan Guruswami, C. Pandu Rangan, M. S. Chang, G. J. Chang, C. K. Wong

ABSTRACT

For a fixed integer r≥2, the Kr-packing problem is to find the maximum number of pairwise vertex-disjointKr's (complete graphs on r vertices) in a given graph. The Kr-factor problem asks for the existence of a partition of the vertex set of a graph into Kr's. The Kr-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r≥3 – it is known that for r≥3 the Kr-factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the Kr-packing problem on restricted classes of graphs.We first prove that for r≥3 the Kr-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K3-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K3-packing and the Kr-factor problems on split graphs (this is interesting in light of the fact that Kr-packing becomes NP-complete on split graphs for r≥4), and for the Kr-packing problem on cographs. More... »

PAGES

79-89

References to SciGraph publications

  • 1998. The Vertex-Disjoint Triangles Problem in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s006070170039

    DOI

    http://dx.doi.org/10.1007/s006070170039

    DIMENSIONS

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


    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": "MIT Laboratory for Computer Science Cambridge, MA 01239, USA venkat@theory.lcs.mit.edu, US", 
              "id": "http://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "MIT Laboratory for Computer Science Cambridge, MA 01239, USA venkat@theory.lcs.mit.edu, US"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Guruswami", 
            "givenName": "Venkatesan", 
            "id": "sg:person.015711462165.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015711462165.98"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering Indian Institute of Technology Madras-600 036, India rangan@iitm.ernet.in, IN", 
              "id": "http://www.grid.ac/institutes/None", 
              "name": [
                "Department of Computer Science and Engineering Indian Institute of Technology Madras-600 036, India rangan@iitm.ernet.in, IN"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pandu Rangan", 
            "givenName": "C.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering National Chung Cheng University Ming-Hsiun, Chiayi 621 Taiwan, Republic of China mschang@cs.ccu.edu.tw, TW", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "Department of Computer Science and Information Engineering National Chung Cheng University Ming-Hsiun, Chiayi 621 Taiwan, Republic of China mschang@cs.ccu.edu.tw, TW"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "M. S.", 
            "id": "sg:person.013174232477.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Applied Mathematics National Chaio Tung University Hsinchu 30050 Taiwan, Republic of China gjchang@math.nctu.edu.tw, TW", 
              "id": "http://www.grid.ac/institutes/grid.260539.b", 
              "name": [
                "Department of Applied Mathematics National Chaio Tung University Hsinchu 30050 Taiwan, Republic of China gjchang@math.nctu.edu.tw, TW"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "G. J.", 
            "id": "sg:person.014754575353.20", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014754575353.20"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering Chinese University of Hong Kong, Hong Kong wongck@cse.cuhk.edu.hk, CN", 
              "id": "http://www.grid.ac/institutes/grid.10784.3a", 
              "name": [
                "Department of Computer Science and Engineering Chinese University of Hong Kong, Hong Kong wongck@cse.cuhk.edu.hk, CN"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wong", 
            "givenName": "C. K.", 
            "id": "sg:person.013544314001.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013544314001.98"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/10692760_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015750643", 
              "https://doi.org/10.1007/10692760_3"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001-03", 
        "datePublishedReg": "2001-03-01", 
        "description": "Abstract For a fixed integer r\u22652, the Kr-packing problem is to find the maximum number of pairwise vertex-disjointKr's (complete graphs on r vertices) in a given graph. The Kr-factor problem asks for the existence of a partition of the vertex set of a graph into Kr's. The Kr-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r\u22653 \u2013 it is known that for r\u22653 the Kr-factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the Kr-packing problem on restricted classes of graphs.We first prove that for r\u22653 the Kr-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K3-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K3-packing and the Kr-factor problems on split graphs (this is interesting in light of the fact that Kr-packing becomes NP-complete on split graphs for r\u22654), and for the Kr-packing problem on cographs.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s006070170039", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1297324", 
            "issn": [
              "0010-485X", 
              "1436-5057"
            ], 
            "name": "Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "66"
          }
        ], 
        "keywords": [
          "classical matching problem", 
          "matching problem", 
          "polynomial algorithm", 
          "graph", 
          "hardness results", 
          "class of graphs", 
          "chordal graphs", 
          "split graphs", 
          "planar graphs", 
          "NP", 
          "line graphs", 
          "algorithm", 
          "maximum number", 
          "complexity", 
          "cographs", 
          "partition", 
          "open question", 
          "natural generalization", 
          "vertices", 
          "generalization", 
          "integers", 
          "class", 
          "number", 
          "total graph", 
          "results", 
          "questions", 
          "number R", 
          "existence", 
          "Kr", 
          "problem", 
          "paper", 
          "pairwise vertex-disjointKr's", 
          "vertex-disjointKr's", 
          "Kr-factor problem", 
          "Kr-packing problem", 
          "clique number r", 
          "K3-packing"
        ], 
        "name": "The Kr-Packing Problem", 
        "pagination": "79-89", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1041903303"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s006070170039"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s006070170039", 
          "https://app.dimensions.ai/details/publication/pub.1041903303"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_336.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s006070170039"
      }
    ]
     

    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/s006070170039'

    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/s006070170039'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s006070170039'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s006070170039'


     

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

    138 TRIPLES      22 PREDICATES      64 URIs      55 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s006070170039 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N3978b61685b04480a3d44df229623134
    4 schema:citation sg:pub.10.1007/10692760_3
    5 schema:datePublished 2001-03
    6 schema:datePublishedReg 2001-03-01
    7 schema:description Abstract For a fixed integer r≥2, the Kr-packing problem is to find the maximum number of pairwise vertex-disjointKr's (complete graphs on r vertices) in a given graph. The Kr-factor problem asks for the existence of a partition of the vertex set of a graph into Kr's. The Kr-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r≥3 – it is known that for r≥3 the Kr-factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the Kr-packing problem on restricted classes of graphs.We first prove that for r≥3 the Kr-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K3-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K3-packing and the Kr-factor problems on split graphs (this is interesting in light of the fact that Kr-packing becomes NP-complete on split graphs for r≥4), and for the Kr-packing problem on cographs.
    8 schema:genre article
    9 schema:inLanguage en
    10 schema:isAccessibleForFree false
    11 schema:isPartOf N0d8eb54b987f4140be4f9b41a485fa21
    12 N8cf7fdd089a844c8ba0abb4ddfe20f6b
    13 sg:journal.1297324
    14 schema:keywords K3-packing
    15 Kr
    16 Kr-factor problem
    17 Kr-packing problem
    18 NP
    19 algorithm
    20 chordal graphs
    21 class
    22 class of graphs
    23 classical matching problem
    24 clique number r
    25 cographs
    26 complexity
    27 existence
    28 generalization
    29 graph
    30 hardness results
    31 integers
    32 line graphs
    33 matching problem
    34 maximum number
    35 natural generalization
    36 number
    37 number R
    38 open question
    39 pairwise vertex-disjointKr's
    40 paper
    41 partition
    42 planar graphs
    43 polynomial algorithm
    44 problem
    45 questions
    46 results
    47 split graphs
    48 total graph
    49 vertex-disjointKr's
    50 vertices
    51 schema:name The Kr-Packing Problem
    52 schema:pagination 79-89
    53 schema:productId N5a3929698fbd4c399524bb1c7395a9ce
    54 Na17cba7851834b6baadd706e05be63a9
    55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041903303
    56 https://doi.org/10.1007/s006070170039
    57 schema:sdDatePublished 2021-11-01T18:04
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher N245d417bf70b483fab2e5e63f142f551
    60 schema:url https://doi.org/10.1007/s006070170039
    61 sgo:license sg:explorer/license/
    62 sgo:sdDataset articles
    63 rdf:type schema:ScholarlyArticle
    64 N0d8eb54b987f4140be4f9b41a485fa21 schema:issueNumber 1
    65 rdf:type schema:PublicationIssue
    66 N245d417bf70b483fab2e5e63f142f551 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 N3978b61685b04480a3d44df229623134 rdf:first sg:person.015711462165.98
    69 rdf:rest Na487892a850345dbb93b06d869df4f13
    70 N5a3929698fbd4c399524bb1c7395a9ce schema:name doi
    71 schema:value 10.1007/s006070170039
    72 rdf:type schema:PropertyValue
    73 N5e42185838a84bcba013036ef7194303 schema:affiliation grid-institutes:None
    74 schema:familyName Pandu Rangan
    75 schema:givenName C.
    76 rdf:type schema:Person
    77 N7b2ba1fc0ddb44a9b0795b32c0dbd72d rdf:first sg:person.013174232477.45
    78 rdf:rest Nead86cd289784ccc8d3641e39802a9a9
    79 N8cf7fdd089a844c8ba0abb4ddfe20f6b schema:volumeNumber 66
    80 rdf:type schema:PublicationVolume
    81 Na17cba7851834b6baadd706e05be63a9 schema:name dimensions_id
    82 schema:value pub.1041903303
    83 rdf:type schema:PropertyValue
    84 Na487892a850345dbb93b06d869df4f13 rdf:first N5e42185838a84bcba013036ef7194303
    85 rdf:rest N7b2ba1fc0ddb44a9b0795b32c0dbd72d
    86 Ndbee9f9f7eb84f4686411cf81b937b93 rdf:first sg:person.013544314001.98
    87 rdf:rest rdf:nil
    88 Nead86cd289784ccc8d3641e39802a9a9 rdf:first sg:person.014754575353.20
    89 rdf:rest Ndbee9f9f7eb84f4686411cf81b937b93
    90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Information and Computing Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Computation Theory and Mathematics
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1297324 schema:issn 0010-485X
    97 1436-5057
    98 schema:name Computing
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
    102 schema:familyName Chang
    103 schema:givenName M. S.
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
    105 rdf:type schema:Person
    106 sg:person.013544314001.98 schema:affiliation grid-institutes:grid.10784.3a
    107 schema:familyName Wong
    108 schema:givenName C. K.
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013544314001.98
    110 rdf:type schema:Person
    111 sg:person.014754575353.20 schema:affiliation grid-institutes:grid.260539.b
    112 schema:familyName Chang
    113 schema:givenName G. J.
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014754575353.20
    115 rdf:type schema:Person
    116 sg:person.015711462165.98 schema:affiliation grid-institutes:grid.116068.8
    117 schema:familyName Guruswami
    118 schema:givenName Venkatesan
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015711462165.98
    120 rdf:type schema:Person
    121 sg:pub.10.1007/10692760_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015750643
    122 https://doi.org/10.1007/10692760_3
    123 rdf:type schema:CreativeWork
    124 grid-institutes:None schema:alternateName Department of Computer Science and Engineering Indian Institute of Technology Madras-600 036, India rangan@iitm.ernet.in, IN
    125 schema:name Department of Computer Science and Engineering Indian Institute of Technology Madras-600 036, India rangan@iitm.ernet.in, IN
    126 rdf:type schema:Organization
    127 grid-institutes:grid.10784.3a schema:alternateName Department of Computer Science and Engineering Chinese University of Hong Kong, Hong Kong wongck@cse.cuhk.edu.hk, CN
    128 schema:name Department of Computer Science and Engineering Chinese University of Hong Kong, Hong Kong wongck@cse.cuhk.edu.hk, CN
    129 rdf:type schema:Organization
    130 grid-institutes:grid.116068.8 schema:alternateName MIT Laboratory for Computer Science Cambridge, MA 01239, USA venkat@theory.lcs.mit.edu, US
    131 schema:name MIT Laboratory for Computer Science Cambridge, MA 01239, USA venkat@theory.lcs.mit.edu, US
    132 rdf:type schema:Organization
    133 grid-institutes:grid.260539.b schema:alternateName Department of Applied Mathematics National Chaio Tung University Hsinchu 30050 Taiwan, Republic of China gjchang@math.nctu.edu.tw, TW
    134 schema:name Department of Applied Mathematics National Chaio Tung University Hsinchu 30050 Taiwan, Republic of China gjchang@math.nctu.edu.tw, TW
    135 rdf:type schema:Organization
    136 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering National Chung Cheng University Ming-Hsiun, Chiayi 621 Taiwan, Republic of China mschang@cs.ccu.edu.tw, TW
    137 schema:name Department of Computer Science and Information Engineering National Chung Cheng University Ming-Hsiun, Chiayi 621 Taiwan, Republic of China mschang@cs.ccu.edu.tw, TW
    138 rdf:type schema:Organization
     




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


    ...