Approximating minimum feedback sets and multi-cuts in directed graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

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

ABSTRACT

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... »

PAGES

14-28

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "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

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




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


...