Classifying subset feedback vertex set for H-free graphs

In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set p...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2024-07, Vol.1003, p.114624, Article 114624
Main Authors: Paesani, Giacomo, Paulusma, Daniël, Rzążewski, Paweł
Format: Article
Language:English
Subjects:
Complexity dichotomy
Feedback vertex set
H-free graph
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c292t-ff49e373aff22cf210dfb110a58458dd56a251852d3a33e0d4d3eb2d2aed48ac3
container_end_page
container_issue
container_start_page 114624
container_title Theoretical computer science
container_volume 1003
creator Paesani, Giacomo
Paulusma, Daniël
Rzążewski, Paweł
description In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)>0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.
doi_str_mv 10.1016/j.tcs.2024.114624
format article
fullrecord <record><control><sourceid>elsevier_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1016_j_tcs_2024_114624</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0304397524002391</els_id><sourcerecordid>S0304397524002391</sourcerecordid><originalsourceid>FETCH-LOGICAL-c292t-ff49e373aff22cf210dfb110a58458dd56a251852d3a33e0d4d3eb2d2aed48ac3</originalsourceid><addsrcrecordid>eNp9j81KxDAUhYMoWEcfwF1eoDW5SfqDKynqCANudB3S5GZMHadDUgfn7e1MXXs3By58h_MRcstZwRkv7_pitKkABrLgXJYgz0jG66rJARp5TjImmMxFU6lLcpVSz6ZTVZmRut2YlII_hO2apu8u4Ug9ouuM_aR7jCP-0NNviHSZ-4hI19HsPtI1ufBmk_DmLxfk_enxrV3mq9fnl_ZhlVtoYMy9lw2KShjvAawHzpzvOGdG1VLVzqnSgOK1AieMEMicdAI7cGDQydpYsSB87rVxSCmi17sYvkw8aM70UV33elLXR3U9q0_M_czgNGwfMOpkA24tuhDRjtoN4R_6F7DrYYM</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Classifying subset feedback vertex set for H-free graphs</title><source>ScienceDirect Freedom Collection</source><creator>Paesani, Giacomo ; Paulusma, Daniël ; Rzążewski, Paweł</creator><creatorcontrib>Paesani, Giacomo ; Paulusma, Daniël ; Rzążewski, Paweł</creatorcontrib><description>In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)&gt;0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/j.tcs.2024.114624</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Complexity dichotomy ; Feedback vertex set ; H-free graph</subject><ispartof>Theoretical computer science, 2024-07, Vol.1003, p.114624, Article 114624</ispartof><rights>2024 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c292t-ff49e373aff22cf210dfb110a58458dd56a251852d3a33e0d4d3eb2d2aed48ac3</cites><orcidid>0000-0001-7696-3848</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail></links><search><creatorcontrib>Paesani, Giacomo</creatorcontrib><creatorcontrib>Paulusma, Daniël</creatorcontrib><creatorcontrib>Rzążewski, Paweł</creatorcontrib><title>Classifying subset feedback vertex set for H-free graphs</title><title>Theoretical computer science</title><description>In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)&gt;0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.</description><subject>Complexity dichotomy</subject><subject>Feedback vertex set</subject><subject>H-free graph</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><recordid>eNp9j81KxDAUhYMoWEcfwF1eoDW5SfqDKynqCANudB3S5GZMHadDUgfn7e1MXXs3By58h_MRcstZwRkv7_pitKkABrLgXJYgz0jG66rJARp5TjImmMxFU6lLcpVSz6ZTVZmRut2YlII_hO2apu8u4Ug9ouuM_aR7jCP-0NNviHSZ-4hI19HsPtI1ufBmk_DmLxfk_enxrV3mq9fnl_ZhlVtoYMy9lw2KShjvAawHzpzvOGdG1VLVzqnSgOK1AieMEMicdAI7cGDQydpYsSB87rVxSCmi17sYvkw8aM70UV33elLXR3U9q0_M_czgNGwfMOpkA24tuhDRjtoN4R_6F7DrYYM</recordid><startdate>20240701</startdate><enddate>20240701</enddate><creator>Paesani, Giacomo</creator><creator>Paulusma, Daniël</creator><creator>Rzążewski, Paweł</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0001-7696-3848</orcidid></search><sort><creationdate>20240701</creationdate><title>Classifying subset feedback vertex set for H-free graphs</title><author>Paesani, Giacomo ; Paulusma, Daniël ; Rzążewski, Paweł</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c292t-ff49e373aff22cf210dfb110a58458dd56a251852d3a33e0d4d3eb2d2aed48ac3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Complexity dichotomy</topic><topic>Feedback vertex set</topic><topic>H-free graph</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Paesani, Giacomo</creatorcontrib><creatorcontrib>Paulusma, Daniël</creatorcontrib><creatorcontrib>Rzążewski, Paweł</creatorcontrib><collection>CrossRef</collection><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Paesani, Giacomo</au><au>Paulusma, Daniël</au><au>Rzążewski, Paweł</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Classifying subset feedback vertex set for H-free graphs</atitle><jtitle>Theoretical computer science</jtitle><date>2024-07-01</date><risdate>2024</risdate><volume>1003</volume><spage>114624</spage><pages>114624-</pages><artnum>114624</artnum><issn>0304-3975</issn><eissn>1879-2294</eissn><abstract>In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)&gt;0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.tcs.2024.114624</doi><orcidid>https://orcid.org/0000-0001-7696-3848</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0304-3975
ispartof Theoretical computer science, 2024-07, Vol.1003, p.114624, Article 114624
issn 0304-3975
1879-2294
language eng
recordid cdi_crossref_primary_10_1016_j_tcs_2024_114624
source ScienceDirect Freedom Collection
subjects Complexity dichotomy
Feedback vertex set
H-free graph
title Classifying subset feedback vertex set for H-free graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-03-05T21%3A47%3A15IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Classifying%20subset%20feedback%20vertex%20set%20for%20H-free%20graphs&rft.jtitle=Theoretical%20computer%20science&rft.au=Paesani,%20Giacomo&rft.date=2024-07-01&rft.volume=1003&rft.spage=114624&rft.pages=114624-&rft.artnum=114624&rft.issn=0304-3975&rft.eissn=1879-2294&rft_id=info:doi/10.1016/j.tcs.2024.114624&rft_dat=%3Celsevier_cross%3ES0304397524002391%3C/elsevier_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c292t-ff49e373aff22cf210dfb110a58458dd56a251852d3a33e0d4d3eb2d2aed48ac3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true