{"id":12738,"date":"2021-11-17T19:22:19","date_gmt":"2021-11-18T00:22:19","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12738"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-255-vc-dimensions-for-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-255-vc-dimensions-for-graphs\/","title":{"rendered":"TR-255: VC-Dimensions for Graphs"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-255: VC-Dimensions for Graphs\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-255<\/strong>
\nNovember 1994<\/p>\n\n\n\n

VC-Dimensions for Graphs<\/h2>\n\n\n\n
\n
\n
Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Jorge Urrutia, Gerhard J. Woeginger<\/div>\n<\/div>\n<\/div>\n\n\n\n
\n

Abstract<\/h3>\n<\/div>\n\n\n\n

We study set systems over the vertex set (or edge set) of some graph that are induced by special graph properties like clique, connectedness, path, star, tree, etc. We derive a variety of combinatorial and computational results on the VC (Vapnik-Chervonenkis) dimension of these set systems.For most of these set systems (e.g. for the systems induced by trees, connected sets, or paths), computing the VC-dimension is an NP-hard problem. Moreover, determining the VC-dimension for set systems induced by neighborhoods of single vertices is complete for the class LogNP. In contrast to these intractability results, we show that the VC-dimension for set systems induced by stars is computable in polynomial time. For set systems induced by paths or cycles, we determine the extremal graphs G with the minimum number of edges such that VCP(G) \u0015 k. Finally, we show a close relation between the VC dimension of set systems induced by connected sets of vertices and the VC dimension of set systems induced by connected sets of edges; the argument is done via the line graph of the corresponding graph.<\/p>\n\n\n\n

TR-255.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-255 November 1994 VC-Dimensions for Graphs Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Jorge Urrutia, Gerhard J. Woeginger Abstract We study set systems over the vertex set (or edge set) of some graph that are induced by special graph properties like clique, connectedness, path, star, tree, etc. We derive a variety of […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11914,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12738","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12738","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12738"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12738\/revisions"}],"predecessor-version":[{"id":12754,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12738\/revisions\/12754"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11914"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12738"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12738"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}