# The Vertex-Disjoint Triangles Problem

Ontology type: schema:Chapter

### Chapter Info

DATE

1998

AUTHORS ABSTRACT

The vertex-disjoint triangles (VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G. The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. It is known that the triangle cover problem is NP-complete on general graphs with clique number 3 [6]. The VDT problem is MAX SNP-hard on graphs with maximum degree four, while it can be approximated within 3/2+ε, for any ε > 0, in polynomial time [11].We prove that the VDT problem is NP-complete even when the input graphs are chordal, planar, line or total graphs. We present an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $O(m \sqrt{n})$ \end{document} algorithm for the VDT problem on split graphs and an O(n3) algorithm for the VDT problem on cographs. A linear algorithm for the triangle cover problem on strongly chordal graphs is also presented. Finally, the notion of packing-hardness, which may be crucial to the understanding of the difficulty of generalized matching problems, is defined. More... »

PAGES

26-37

### Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-65195-6
978-3-540-49494-2

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/10692760_3

DOI

http://dx.doi.org/10.1007/10692760_3

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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": "Dept. of Computer Science & Engg, Indian Institute of Technology, 600 036, Madras, India",
"id": "http://www.grid.ac/institutes/grid.417969.4",
"name": [
"Dept. of Computer Science & Engg, Indian Institute of Technology, 600 036, Madras, India"
],
"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": "Dept. of Computer Science & Engg, Indian Institute of Technology, 600 036, Madras, India",
"id": "http://www.grid.ac/institutes/grid.417969.4",
"name": [
"Dept. of Computer Science & Engg, Indian Institute of Technology, 600 036, Madras, India"
],
"type": "Organization"
},
"familyName": "Rangan",
"givenName": "C. Pandu",
"id": "sg:person.016366027737.61",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Dept. of Computer Science and Information Engg., National Chung Cheng University, Ming-Hsiun, Chiayi 621, Taiwan, Republic of China",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"Dept. of Computer Science and Information Engg., National Chung Cheng University, Ming-Hsiun, Chiayi 621, Taiwan, Republic of China"
],
"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": "Dept. of Computer Science, National Chio-Tung University, Taiwan, Republic of China",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Dept. of Computer Science, National Chio-Tung University, Taiwan, Republic of China"
],
"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": "Dept. of Computer Science and Engg, Chinese University of Hong Kong, Hong Kong",
"id": "http://www.grid.ac/institutes/grid.10784.3a",
"name": [
"Dept. of Computer Science and Engg, Chinese University of Hong Kong, Hong Kong"
],
"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"
}
],
"datePublished": "1998",
"datePublishedReg": "1998-01-01",
"description": "The vertex-disjoint triangles (VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G. The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. It is known that the triangle cover problem is NP-complete on general graphs with clique number 3 [6]. The VDT problem is MAX SNP-hard on graphs with maximum degree four, while it can be approximated within 3/2+\u03b5, for any \u03b5 > 0, in polynomial time [11].We prove that the VDT problem is NP-complete even when the input graphs are chordal, planar, line or total graphs. We present an \\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}\n$O(m \\sqrt{n})$\n\\end{document} algorithm for the VDT problem on split graphs and an O(n3) algorithm for the VDT problem on cographs. A linear algorithm for the triangle cover problem on strongly chordal graphs is also presented. Finally, the notion of packing-hardness, which may be crucial to the understanding of the difficulty of generalized matching problems, is defined.",
"editor": [
{
"familyName": "Hromkovi\u010d",
"givenName": "Juraj",
"type": "Person"
},
{
"familyName": "S\u00fdkora",
"givenName": "Ondrej",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/10692760_3",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-65195-6",
"978-3-540-49494-2"
],
"name": "Graph-Theoretic Concepts in Computer Science",
"type": "Book"
},
"keywords": [
"cover problem",
"polynomial time",
"input graph",
"matching problem",
"general graphs",
"graph",
"MAX SNP",
"algorithm",
"linear algorithm",
"triangle problem",
"split graphs",
"chordal graphs",
"maximum degree four",
"graph G.",
"NP",
"maximum number",
"triangle packing",
"cographs",
"set",
"degree four",
"triangle",
"notion",
"difficulties",
"number",
"time",
"total graph",
"planar",
"lines",
"understanding",
"existence",
"number 3",
"four",
"G.",
"packing",
"SNPs",
"problem",
"vertex-disjoint triangles (VDT) problem",
"pairwise vertex-disjoint triangles",
"vertex-disjoint triangles",
"triangle cover problem",
"perfect triangle packing",
"clique number 3",
"VDT problem"
],
"name": "The Vertex-Disjoint Triangles Problem",
"pagination": "26-37",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1015750643"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/10692760_3"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/10692760_3",
"https://app.dimensions.ai/details/publication/pub.1015750643"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:50",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_193.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/10692760_3"
}
]

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/10692760_3'

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/10692760_3'

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

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

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

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

145 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N3f02e18938bf4fbca649696bc543369b
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description The vertex-disjoint triangles (VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G. The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. It is known that the triangle cover problem is NP-complete on general graphs with clique number 3 [6]. The VDT problem is MAX SNP-hard on graphs with maximum degree four, while it can be approximated within 3/2+ε, for any ε > 0, in polynomial time [11].We prove that the VDT problem is NP-complete even when the input graphs are chordal, planar, line or total graphs. We present an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $O(m \sqrt{n})$ \end{document} algorithm for the VDT problem on split graphs and an O(n3) algorithm for the VDT problem on cographs. A linear algorithm for the triangle cover problem on strongly chordal graphs is also presented. Finally, the notion of packing-hardness, which may be crucial to the understanding of the difficulty of generalized matching problems, is defined.
7 schema:editor N91eab326dffa4f23a1704263db7f1800
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne9057cbd859849769f1a8730f4c0d014
12 schema:keywords G.
13 MAX SNP
14 NP
15 SNPs
16 VDT problem
17 algorithm
18 chordal graphs
19 clique number 3
20 cographs
21 cover problem
22 degree four
23 difficulties
24 existence
25 four
26 general graphs
27 graph
28 graph G.
29 input graph
30 linear algorithm
31 lines
32 matching problem
33 maximum degree four
34 maximum number
35 notion
36 number
37 number 3
38 packing
39 pairwise vertex-disjoint triangles
40 perfect triangle packing
41 planar
42 polynomial time
43 problem
44 set
45 split graphs
46 time
47 total graph
48 triangle
49 triangle cover problem
50 triangle packing
51 triangle problem
52 understanding
53 vertex-disjoint triangles
54 vertex-disjoint triangles (VDT) problem
55 schema:name The Vertex-Disjoint Triangles Problem
56 schema:pagination 26-37
57 schema:productId N65fef68c18e94a9fa2860f0a2a4b9eca
58 Nbb49e29a21ab4febbd8d3dc31d695322
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015750643
61 https://doi.org/10.1007/10692760_3
62 schema:sdDatePublished 2021-11-01T18:50
64 schema:sdPublisher N38c45f8d84ea493fa41826ccc4a7c1fd
65 schema:url https://doi.org/10.1007/10692760_3
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N099203947b514d1db87604195987d16b rdf:first sg:person.013544314001.98
70 rdf:rest rdf:nil
71 N1887c85e98b0484eb77beff84fa3970f rdf:first sg:person.013174232477.45
72 rdf:rest N82d92cf9dcd54d78af2c1567f43012b0
73 N2ce415576087465db67e51ed8d23748a rdf:first Nf43feae8157149728d1834121a91d22b
74 rdf:rest rdf:nil
75 N38c45f8d84ea493fa41826ccc4a7c1fd schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N3f02e18938bf4fbca649696bc543369b rdf:first sg:person.015711462165.98
80 rdf:type schema:Organisation
81 N65fef68c18e94a9fa2860f0a2a4b9eca schema:name doi
82 schema:value 10.1007/10692760_3
83 rdf:type schema:PropertyValue
84 N82d92cf9dcd54d78af2c1567f43012b0 rdf:first sg:person.014754575353.20
85 rdf:rest N099203947b514d1db87604195987d16b
87 rdf:rest N2ce415576087465db67e51ed8d23748a
89 schema:givenName Juraj
90 rdf:type schema:Person
91 Nbb49e29a21ab4febbd8d3dc31d695322 schema:name dimensions_id
92 schema:value pub.1015750643
93 rdf:type schema:PropertyValue
95 rdf:rest N1887c85e98b0484eb77beff84fa3970f
96 Ne9057cbd859849769f1a8730f4c0d014 schema:isbn 978-3-540-49494-2
97 978-3-540-65195-6
98 schema:name Graph-Theoretic Concepts in Computer Science
99 rdf:type schema:Book
100 Nf43feae8157149728d1834121a91d22b schema:familyName Sýkora
101 schema:givenName Ondrej
102 rdf:type schema:Person
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
107 schema:name Computation Theory and Mathematics
108 rdf:type schema:DefinedTerm
109 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
110 schema:familyName Chang
111 schema:givenName M. S.
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
113 rdf:type schema:Person
114 sg:person.013544314001.98 schema:affiliation grid-institutes:grid.10784.3a
115 schema:familyName Wong
116 schema:givenName C. K.
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013544314001.98
118 rdf:type schema:Person
119 sg:person.014754575353.20 schema:affiliation grid-institutes:None
120 schema:familyName Chang
121 schema:givenName G. J.
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014754575353.20
123 rdf:type schema:Person
124 sg:person.015711462165.98 schema:affiliation grid-institutes:grid.417969.4
125 schema:familyName Guruswami
126 schema:givenName Venkatesan
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015711462165.98
128 rdf:type schema:Person
129 sg:person.016366027737.61 schema:affiliation grid-institutes:grid.417969.4
130 schema:familyName Rangan
131 schema:givenName C. Pandu
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61
133 rdf:type schema:Person
134 grid-institutes:None schema:alternateName Dept. of Computer Science, National Chio-Tung University, Taiwan, Republic of China
135 schema:name Dept. of Computer Science, National Chio-Tung University, Taiwan, Republic of China
136 rdf:type schema:Organization
137 grid-institutes:grid.10784.3a schema:alternateName Dept. of Computer Science and Engg, Chinese University of Hong Kong, Hong Kong
138 schema:name Dept. of Computer Science and Engg, Chinese University of Hong Kong, Hong Kong
139 rdf:type schema:Organization
140 grid-institutes:grid.412047.4 schema:alternateName Dept. of Computer Science and Information Engg., National Chung Cheng University, Ming-Hsiun, Chiayi 621, Taiwan, Republic of China
141 schema:name Dept. of Computer Science and Information Engg., National Chung Cheng University, Ming-Hsiun, Chiayi 621, Taiwan, Republic of China
142 rdf:type schema:Organization
143 grid-institutes:grid.417969.4 schema:alternateName Dept. of Computer Science & Engg, Indian Institute of Technology, 600 036, Madras, India
144 schema:name Dept. of Computer Science & Engg, Indian Institute of Technology, 600 036, Madras, India
145 rdf:type schema:Organization