Ontology type: schema:Chapter

1995

Guy Even , Joseph (Seffi) Naor , Baruch Schieber , Madhu Sudan

This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set problem (FES). In the FVS (resp. FES) problem, one is given a directed graph with weights on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-Hard problems and have many applications. We also consider a generalization of these problems: SUBSET-FVS and SUBSET-FVS, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset contains all the cycles that go through a distinguished input subset of vertices and edges. We present approximation algorithms for all four problems that achieve an approximation factor of O(min{log τ* log log τ*, log n log log n)}, where τ* denotes the value of the optimum fractional solution of the problem at hand. For the SUBSET-FVS and SUBSET-FVS problems we also give an algorithm that achieves an approximation factor of O(log2 ‖X‖), where X is the subset of distinguished vertices and edges. This algorithm is based on an approximation algorithm for the multi-cut problem in a special type of directed networks. Another contribution of our paper is a combinatorial algorithm that computes a (1 + ε) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution. More... »

14-28

Integer Programming and Combinatorial Optimization

978-3-540-59408-6

978-3-540-49245-0

http://scigraph.springernature.com/pub.10.1007/3-540-59408-6_38

http://dx.doi.org/10.1007/3-540-59408-6_38

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

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": "Computer Science Dept., Technion, 32000, Haifa, Israel",
"id": "http://www.grid.ac/institutes/grid.6451.6",
"name": [
"Computer Science Dept., Technion, 32000, Haifa, Israel"
],
"type": "Organization"
},
"familyName": "Even",
"givenName": "Guy",
"id": "sg:person.016331307003.74",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016331307003.74"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Computer Science Dept., Technion, 32000, Haifa, Israel",
"id": "http://www.grid.ac/institutes/grid.6451.6",
"name": [
"Computer Science Dept., Technion, 32000, Haifa, Israel"
],
"type": "Organization"
},
"familyName": "Naor",
"givenName": "Joseph (Seffi)",
"id": "sg:person.012454545165.12",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012454545165.12"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IBM Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY",
"id": "http://www.grid.ac/institutes/grid.481554.9",
"name": [
"IBM Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY"
],
"type": "Organization"
},
"familyName": "Schieber",
"givenName": "Baruch",
"id": "sg:person.013362327461.43",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013362327461.43"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IBM Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY",
"id": "http://www.grid.ac/institutes/grid.481554.9",
"name": [
"IBM Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY"
],
"type": "Organization"
},
"familyName": "Sudan",
"givenName": "Madhu",
"id": "sg:person.014663420265.17",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
],
"type": "Person"
}
],
"datePublished": "1995",
"datePublishedReg": "1995-01-01",
"description": "This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set problem (FES). In the FVS (resp. FES) problem, one is given a directed graph with weights on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-Hard problems and have many applications. We also consider a generalization of these problems: SUBSET-FVS and SUBSET-FVS, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset contains all the cycles that go through a distinguished input subset of vertices and edges. We present approximation algorithms for all four problems that achieve an approximation factor of O(min{log \u03c4* log log \u03c4*, log n log log n)}, where \u03c4* denotes the value of the optimum fractional solution of the problem at hand. For the SUBSET-FVS and SUBSET-FVS problems we also give an algorithm that achieves an approximation factor of O(log2 \u2016X\u2016), where X is the subset of distinguished vertices and edges. This algorithm is based on an approximation algorithm for the multi-cut problem in a special type of directed networks. Another contribution of our paper is a combinatorial algorithm that computes a (1 + \u03b5) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution.",
"editor": [
{
"familyName": "Balas",
"givenName": "Egon",
"type": "Person"
},
{
"familyName": "Clausen",
"givenName": "Jens",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/3-540-59408-6_38",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-59408-6",
"978-3-540-49245-0"
],
"name": "Integer Programming and Combinatorial Optimization",
"type": "Book"
},
"keywords": [
"feedback set",
"approximation algorithm",
"set problem",
"NP-hard problem",
"classical NP-hard problem",
"approximation factor",
"optimum fractional solution",
"Feedback Vertex Set problem",
"general linear programming methods",
"FVS problem",
"subset of vertices",
"combinatorial algorithm",
"algorithm",
"minimum total weight",
"weighted feedback vertex set problem",
"programming method",
"feedback vertex",
"graph",
"fractional solution",
"input subset",
"linear programming method",
"related problems",
"approximate solution",
"set",
"vertices",
"distinguished vertices",
"special type",
"network",
"solution",
"subset",
"edge",
"applications",
"generalization",
"method",
"hand",
"total weight",
"approximation",
"contribution",
"types",
"weight",
"cycle",
"values",
"factors",
"problem",
"paper",
"vertex set (FVS) problem",
"weighted feedback edge set problem",
"feedback edge set problem",
"edge set problem",
"SUBSET-FVS",
"distinguished input subset",
"SUBSET-FVS problems",
"multi-cut problem",
"fractional optimal feedback vertex",
"optimal feedback vertex",
"minimum feedback sets"
],
"name": "Approximating minimum feedback sets and multi-cuts in directed graphs",
"pagination": "14-28",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1025624715"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/3-540-59408-6_38"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/3-540-59408-6_38",
"https://app.dimensions.ai/details/publication/pub.1025624715"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-01-01T19:13",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_226.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/3-540-59408-6_38"
}
]
```

Download the RDF metadata as: json-ld nt turtle xml License info

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/3-540-59408-6_38'

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/3-540-59408-6_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-59408-6_38'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-59408-6_38'

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

145 TRIPLES
23 PREDICATES
82 URIs
75 LITERALS
7 BLANK NODES

Subject | Predicate | Object | |
---|---|---|---|

1 | sg:pub.10.1007/3-540-59408-6_38 | schema:about | anzsrc-for:08 |

2 | ″ | ″ | anzsrc-for:0802 |

3 | ″ | schema:author | N4baf4ca256d248809343542702dc0ff9 |

4 | ″ | schema:datePublished | 1995 |

5 | ″ | schema:datePublishedReg | 1995-01-01 |

6 | ″ | schema:description | This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set problem (FES). In the FVS (resp. FES) problem, one is given a directed graph with weights on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-Hard problems and have many applications. We also consider a generalization of these problems: SUBSET-FVS and SUBSET-FVS, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset contains all the cycles that go through a distinguished input subset of vertices and edges. We present approximation algorithms for all four problems that achieve an approximation factor of O(min{log τ* log log τ*, log n log log n)}, where τ* denotes the value of the optimum fractional solution of the problem at hand. For the SUBSET-FVS and SUBSET-FVS problems we also give an algorithm that achieves an approximation factor of O(log2 ‖X‖), where X is the subset of distinguished vertices and edges. This algorithm is based on an approximation algorithm for the multi-cut problem in a special type of directed networks. Another contribution of our paper is a combinatorial algorithm that computes a (1 + ε) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution. |

7 | ″ | schema:editor | Na69f15e87e124972a27fac1e728388ef |

8 | ″ | schema:genre | chapter |

9 | ″ | schema:inLanguage | en |

10 | ″ | schema:isAccessibleForFree | false |

11 | ″ | schema:isPartOf | N330db72409054b6ab274ce486bcad8fb |

12 | ″ | schema:keywords | FVS problem |

13 | ″ | ″ | Feedback Vertex Set problem |

14 | ″ | ″ | NP-hard problem |

15 | ″ | ″ | SUBSET-FVS |

16 | ″ | ″ | SUBSET-FVS problems |

17 | ″ | ″ | algorithm |

18 | ″ | ″ | applications |

19 | ″ | ″ | approximate solution |

20 | ″ | ″ | approximation |

21 | ″ | ″ | approximation algorithm |

22 | ″ | ″ | approximation factor |

23 | ″ | ″ | classical NP-hard problem |

24 | ″ | ″ | combinatorial algorithm |

25 | ″ | ″ | contribution |

26 | ″ | ″ | cycle |

27 | ″ | ″ | distinguished input subset |

28 | ″ | ″ | distinguished vertices |

29 | ″ | ″ | edge |

30 | ″ | ″ | edge set problem |

31 | ″ | ″ | factors |

32 | ″ | ″ | feedback edge set problem |

33 | ″ | ″ | feedback set |

34 | ″ | ″ | feedback vertex |

35 | ″ | ″ | fractional optimal feedback vertex |

36 | ″ | ″ | fractional solution |

37 | ″ | ″ | general linear programming methods |

38 | ″ | ″ | generalization |

39 | ″ | ″ | graph |

40 | ″ | ″ | hand |

41 | ″ | ″ | input subset |

42 | ″ | ″ | linear programming method |

43 | ″ | ″ | method |

44 | ″ | ″ | minimum feedback sets |

45 | ″ | ″ | minimum total weight |

46 | ″ | ″ | multi-cut problem |

47 | ″ | ″ | network |

48 | ″ | ″ | optimal feedback vertex |

49 | ″ | ″ | optimum fractional solution |

50 | ″ | ″ | paper |

51 | ″ | ″ | problem |

52 | ″ | ″ | programming method |

53 | ″ | ″ | related problems |

54 | ″ | ″ | set |

55 | ″ | ″ | set problem |

56 | ″ | ″ | solution |

57 | ″ | ″ | special type |

58 | ″ | ″ | subset |

59 | ″ | ″ | subset of vertices |

60 | ″ | ″ | total weight |

61 | ″ | ″ | types |

62 | ″ | ″ | values |

63 | ″ | ″ | vertex set (FVS) problem |

64 | ″ | ″ | vertices |

65 | ″ | ″ | weight |

66 | ″ | ″ | weighted feedback edge set problem |

67 | ″ | ″ | weighted feedback vertex set problem |

68 | ″ | schema:name | Approximating minimum feedback sets and multi-cuts in directed graphs |

69 | ″ | schema:pagination | 14-28 |

70 | ″ | schema:productId | N3d99a8f54f7349e3b21d5077883f7a14 |

71 | ″ | ″ | Ndcad337a6c2d4600afc8ca4e1cf0f344 |

72 | ″ | schema:publisher | N23add9a3137649288a76b0ccdf201743 |

73 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1025624715 |

74 | ″ | ″ | https://doi.org/10.1007/3-540-59408-6_38 |

75 | ″ | schema:sdDatePublished | 2022-01-01T19:13 |

76 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |

77 | ″ | schema:sdPublisher | N6bd7a644dc8f4fafad8e993d2a40ad87 |

78 | ″ | schema:url | https://doi.org/10.1007/3-540-59408-6_38 |

79 | ″ | sgo:license | sg:explorer/license/ |

80 | ″ | sgo:sdDataset | chapters |

81 | ″ | rdf:type | schema:Chapter |

82 | N23add9a3137649288a76b0ccdf201743 | schema:name | Springer Nature |

83 | ″ | rdf:type | schema:Organisation |

84 | N330db72409054b6ab274ce486bcad8fb | schema:isbn | 978-3-540-49245-0 |

85 | ″ | ″ | 978-3-540-59408-6 |

86 | ″ | schema:name | Integer Programming and Combinatorial Optimization |

87 | ″ | rdf:type | schema:Book |

88 | N3d99a8f54f7349e3b21d5077883f7a14 | schema:name | doi |

89 | ″ | schema:value | 10.1007/3-540-59408-6_38 |

90 | ″ | rdf:type | schema:PropertyValue |

91 | N4baf4ca256d248809343542702dc0ff9 | rdf:first | sg:person.016331307003.74 |

92 | ″ | rdf:rest | N8b812941d1bf4806a780d187ffa616a4 |

93 | N6bd7a644dc8f4fafad8e993d2a40ad87 | schema:name | Springer Nature - SN SciGraph project |

94 | ″ | rdf:type | schema:Organization |

95 | N8b812941d1bf4806a780d187ffa616a4 | rdf:first | sg:person.012454545165.12 |

96 | ″ | rdf:rest | Nf65880020dca49b29c76b9f591484d4f |

97 | N958e05e3e0764e3cbddbc147cc48a9c3 | schema:familyName | Clausen |

98 | ″ | schema:givenName | Jens |

99 | ″ | rdf:type | schema:Person |

100 | Na69f15e87e124972a27fac1e728388ef | rdf:first | Ndd9ab1890f2448bd8f58f3dfa79752be |

101 | ″ | rdf:rest | Nf971c97af99e45a9bd525ad15946a7eb |

102 | Ndcad337a6c2d4600afc8ca4e1cf0f344 | schema:name | dimensions_id |

103 | ″ | schema:value | pub.1025624715 |

104 | ″ | rdf:type | schema:PropertyValue |

105 | Ndd9ab1890f2448bd8f58f3dfa79752be | schema:familyName | Balas |

106 | ″ | schema:givenName | Egon |

107 | ″ | rdf:type | schema:Person |

108 | Nf65880020dca49b29c76b9f591484d4f | rdf:first | sg:person.013362327461.43 |

109 | ″ | rdf:rest | Nfbd790082d3944bcbba7f68a29e0c8e8 |

110 | Nf971c97af99e45a9bd525ad15946a7eb | rdf:first | N958e05e3e0764e3cbddbc147cc48a9c3 |

111 | ″ | rdf:rest | rdf:nil |

112 | Nfbd790082d3944bcbba7f68a29e0c8e8 | rdf:first | sg:person.014663420265.17 |

113 | ″ | rdf:rest | rdf:nil |

114 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |

115 | ″ | schema:name | Information and Computing Sciences |

116 | ″ | rdf:type | schema:DefinedTerm |

117 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |

118 | ″ | schema:name | Computation Theory and Mathematics |

119 | ″ | rdf:type | schema:DefinedTerm |

120 | sg:person.012454545165.12 | schema:affiliation | grid-institutes:grid.6451.6 |

121 | ″ | schema:familyName | Naor |

122 | ″ | schema:givenName | Joseph (Seffi) |

123 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012454545165.12 |

124 | ″ | rdf:type | schema:Person |

125 | sg:person.013362327461.43 | schema:affiliation | grid-institutes:grid.481554.9 |

126 | ″ | schema:familyName | Schieber |

127 | ″ | schema:givenName | Baruch |

128 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013362327461.43 |

129 | ″ | rdf:type | schema:Person |

130 | sg:person.014663420265.17 | schema:affiliation | grid-institutes:grid.481554.9 |

131 | ″ | schema:familyName | Sudan |

132 | ″ | schema:givenName | Madhu |

133 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17 |

134 | ″ | rdf:type | schema:Person |

135 | sg:person.016331307003.74 | schema:affiliation | grid-institutes:grid.6451.6 |

136 | ″ | schema:familyName | Even |

137 | ″ | schema:givenName | Guy |

138 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016331307003.74 |

139 | ″ | rdf:type | schema:Person |

140 | grid-institutes:grid.481554.9 | schema:alternateName | IBM Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY |

141 | ″ | schema:name | IBM Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY |

142 | ″ | rdf:type | schema:Organization |

143 | grid-institutes:grid.6451.6 | schema:alternateName | Computer Science Dept., Technion, 32000, Haifa, Israel |

144 | ″ | schema:name | Computer Science Dept., Technion, 32000, Haifa, Israel |

145 | ″ | rdf:type | schema:Organization |