Forest Covers and Bounded Forest Covers

Barun Gorain; Daya Ram Gaur; Rishi Ranjan Singh; Shaswati Patra

REVIEW 4 major objections 5 minor 27 references

Forest Covers and Bounded Forest Covers

T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The forest cover problem admits a deterministic 2-approximation via LP rounding, matching the inapproximability inherited from vertex cover.

desk verdict A natural vertex-cover generalization with a likely-tight 2-approximation, but the deterministic proof is unverifiable as written and the probabilistic theorem is wrong as written. read the letter →

arxiv 2411.16578 v1 pith:HA3BDQVI submitted 2024-11-25 cs.DS cs.CCmath.CO

Daya Ram Gaur , Barun Gorain , Shaswati Patra , Rishi Ranjan Singh This is my paper · ORCID

classification cs.DScs.CCmath.CO MSC 68W2568Q1790C27

keywords forestcoverboundedapproximationalgorithmLProundingdualfittingprobabilisticmethodvertexminimumspanningtree

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies two NP-complete covering problems: forest cover, where a forest's vertices must cover all edges and the cost is the number of vertices plus a weight-discounted edge count, and bounded forest cover, where each tree in the covering forest may weigh at most λ. It claims that forest cover admits a randomized (2+ε)-approximation via dual fitting on randomly rounded binary-weight instances, a deterministic 2-approximation by rounding an LP solution through component-wise minimum spanning trees and pruning low-value pendant vertices, and, as a consequence, a 6-approximation for bounded forest cover. If the deterministic 2-approximation is correct, the approximation ratio of forest cover is exactly 2, matching the hardness inherited from vertex cover. The probabilistic averaging technique is presented as a contribution that may be of independent use.

What carries the argument

The load-bearing objects are the LP relaxation with three constraint families — vertex cover constraints x_u + x_v ≥ 1, incidence constraints x_i ≥ y_ij, and cycle-elimination constraints for every nonempty vertex set S — and the component-wise MST-plus-prune rounding. For the probabilistic result, the mechanism is dual fitting on randomly rounded binary-weight instances: each edge weight is replaced by an independent Bernoulli(1 − w_e) indicator, the binary-weight primal-dual Algorithm 1 gives a feasible dual of value k + |M|, and averaging m = n/(2δ²) such dual solutions produces a feasible dual for a δ-perturbed LP, yielding a (2+ε)-approximation. For bounded forest cover, the mechanism is an edge-decomposition lemma stating that a tree of weight w with edges of weight at most β splits into at most max{w/β, 1} trees of weight at most 2β.

What would settle it

Run Algorithm 2 on a small weighted graph and check whether the returned forest ever satisfies wi(APX_FC) > 2·LP_OPT, or more directly, search for an LP-optimal support whose MST has, after deleting pendant low-valued vertices, a remaining vertex with x* < 0.5 and degree 1 in the contracted tree; if such an instance exists and the inequality of Lemma 12 fails, the 2-approximation proof collapses.

Watch

Extended reading notes

Core claim

The central discovery is that the weighted index objective — the number of vertices in the forest minus the weight-discounted edge sum, equivalently the component count plus the weighted edge sum — can be rounded from the LP optimum without losing more than a factor of two. The proof works component by component on the support of the optimal fractional solution: an MST is built by Kruskal's algorithm, pendant vertices with fractional value below 1/2 are deleted along with their incident edges, and a loop-invariant argument over the Kruskal edge order shows each remaining tree's cost is at most twice the component's fractional cost. Isolated vertices with fractional value at least 1/2 are kept in the forest, while isolated vertices below 1/2 are discarded. Summing over all components yields the theorem wi(OPT_FC) ≥ (1/2) wi(APX_FC), establishing that Algorithm 2 is a deterministic 2-approximation.

Load-bearing premise

The proof of the key component bound assumes that in the MST built from the LP support, every surviving vertex whose fractional LP value is below 0.5 has degree at least 2 after the tree is contracted; this follows only because the LP's vertex-cover constraint forbids edges joining two low-value vertices, and if that structural fact failed, the Hall's theorem matching step in Lemma 12 would break.

Editorial extensions

If this is right

Every instance of the forest cover problem can be solved in polynomial time to within a factor of 2 of the LP optimum, by solving the LP and applying the component-wise MST rounding.
Because any α-approximation for forest cover would give an α-approximation for vertex cover on unit-weight edges, the ratio 2 cannot be improved without also improving vertex cover's approximation ratio, so the problem is closed under the same hardness assumptions.
The bounded forest cover problem has a 6-approximation algorithm, improving the previous 8-approximation, via edge-decomposing the trees returned by the 2-approximation for forest cover.
The probabilistic dual-fitting scheme implies that with O(n/ε⁴) random experiments, at least one of the produced primal forests is a (2+ε)-approximation with high probability, giving the first approximation factor arbitrarily close to 2 for arbitrary real weights in [0,1].

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the averaging trick over randomized binary-weight duals is not tied to forest cover's specific objective; it should apply to any covering problem that has a 2-approximate primal-dual pair on binary instances and linear dual constraints, provided independent Bernoulli rounding of the right-hand sides is feasible.
Editorial inference: the deterministic proof's component-wise loop invariant suggests a general recipe — round the LP support with a minimum spanning tree, prune low-value leaves, and charge the rounded cost to fractional vertex and edge variables — that may transfer to related tree and path covering problems with vertex costs.
Editorial inference: the 6-factor for bounded forest cover is likely not the end of the line; a tighter edge-decomposition or a better forest-cover approximation would directly lower it, and the 8-to-6 jump suggests trying to close the gap to the forest-cover ratio.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Best to read this as a first draft of a good paper. The forest cover problem is a natural relative of vertex cover: cover all edges with vertices and pay the weighted index of a forest. Unit weights make it exactly vertex cover, so 2 is tight under UGC; the deterministic 2-approximation would close the problem if the proof held. The binary-weight dual fitting argument in Section 3.1 is clean and really does give a 2-approximation for the 0/1 case, and the BFC 6-approximation via scaling plus Lemma 13 is a genuine improvement over the authors' earlier 8, conditional only on the deterministic 2-approximation. The citation pattern is ordinary, and the self-citation to the earlier CALDAM paper is appropriate.

The soft spots are serious. The probabilistic Theorem 4 is wrong as written. The quantity P_i includes a stray 2|M_i| that is not part of the weighted index, so P_i is not the primal objective for experiment i. The proof then averages over m experiments while treating the y variables as fixed, but those variables depend on the random W_i_e. The expectation step is invalid, and I do not see a typo-level repair; one would need a per-experiment bound on the true primal cost. Theorem 4 should be fixed or dropped from the claims.

The deterministic proof is structurally plausible but not verifiable. The reader's worry about Lemma 12's degree claim is less fragile than it looks: a low-low support edge is impossible by x_u+x_v >= 1, and the Hall argument has a short repair. The real broken step is in Lemma 8. Inequality (26) is proved for the prefix H_t via Lemma 9. Lemma 11 gives a suffix edge inequality (32), but nothing gives a suffix analogue of (26) with a component bound, and the move from (38) to (39) simply declares the union of H_t and H_t^bar terms. Without (39), Lemma 8 fails, and with it Lemma 5 and Theorem 5. That is load-bearing. Section 4.2 needs a full rewrite with the definitions fixed; the text around S, S', S'', and ET^A/ET^B is garbled.

Who gets value from this? Researchers working on vertex cover variants, tree cover, and bounded covering problems. The BFC improvement is worth keeping, and the problem definition is worth having in the literature. I would not accept the manuscript in its current form, but I would send a serious referee a revised version: fix or remove Theorem 4, and rewrite Section 4.2 with the prefix/suffix algebra done explicitly. If the deterministic 2-approximation survives that rewrite, this becomes a solid, tight result.

Referee Report

4 major / 5 minor

Summary. The manuscript studies the forest cover problem, in which one chooses a vertex-covering forest minimizing the weighted index wi(F)=Σ|T_i|-Σ_{e∈E(F)}(1-w_e), and the bounded forest cover problem. The claimed contributions are: (1) a randomized (2+ε)-approximation via a dual-fitting argument over binary-weight instances, (2) a deterministic LP-rounding 2-approximation (Theorem 5), and (3) a 6-approximation for bounded forest cover (Theorem 6), improving a known 8-approximation. The deterministic result is presented as the main contribution and is proved through a component-wise inequality (Lemma 5) established by Kruskal-prefix and Hall-type arguments in Section 4.2; the bounded forest cover result depends directly on the deterministic 2-approximation.

Significance. If the deterministic 2-approximation were correct, it would be essentially tight under the standard reduction from vertex cover, and it would imply the stated improvement for bounded forest cover. The paper also attempts a genuinely different probabilistic dual-fitting technique, which could be of independent interest. The lower-bound construction for binary weights (Lemma 2) is clean, and the overall LP-rounding strategy is natural. However, the current manuscript contains load-bearing gaps in both the deterministic and the probabilistic proofs, so the significance is conditional on substantial repair.

major comments (4)

[Section 4.2, Lemma 8] The step from inequalities (26), (32), and (35) to inequality (39) is not valid as written. Inequality (26) is proved only for the prefix H_t. Inequality (32) bounds the suffix edge terms, but no analogue of (26) is derived for the suffix H_t^bar. In the derivation of (36)–(38), the prefix deleted-vertex term Σ_{i∈VD_t} x*_i − Σ_{(i,j)∈ED_t} y*_ij(1−w_ij) is added twice, while the corresponding suffix term Σ_{i∈VD_t^bar} x*_i − Σ_{(i,j)∈ED_t^bar} y*_ij(1−w_ij) never appears. The sentence "To (38), we add terms of sub-graph H_t and H_t^bar" cannot produce the missing suffix term from a duplicated prefix term. Since Lemma 8 is the load-bearing step for Lemma 5 and Theorem 5, the deterministic 2-approximation is not proved as written.
[Section 4.2, Lemma 12] The statement and proof of Lemma 12 are too garbled to verify. The sets S, S′, S′′ and the edge partitions ET^A_t and ET^B_t are defined with conflicting membership conditions, and formula (35) mixes barred and unbarred vertex sets from H_t and H_t^bar. The Hall argument also asserts without a precise proof that every vertex in VT_t^<.5 has degree at least two in the relevant tree, which is plausible from the pruning rule but should be stated for the suffix sets used in (35). Lemma 12 supplies the −Q/2 bound needed to complete inequality (38), so this is not merely a presentation issue.
[Section 3.2, Theorem 4] The expectation step E[y_i^e W_i^e] = y_i^e E[W_i^e] is invalid. Here y_i^e is the output of Algorithm 1 on the random binary instance W_i, so y_i^e and W_i^e are correlated; y_i^e is not a fixed quantity. This breaks the averaged primal-dual inequality P ≤ 2D and the subsequent derivation of the claimed (2+ε)-approximation.
[Section 3.2, Theorem 4] The choice δ = ε² and the assertion that δΣ_e y*_e ≤ ε·OPT for sufficiently small ε are not uniform in the instance size. For example, take a complete graph on N vertices with all edge weights 0. The forest cover optimum is 1, and an optimal LP solution can have x*_i = 1 for every vertex and y*_e = 1 on the edges of a spanning tree, giving Σ_e y*_e = N−1. Then δΣ_e y*_e = ε²(N−1), which exceeds ε for N > 1/ε + 1. Thus OPT′ ≤ (1+ε)OPT is not guaranteed. The parameter δ needs to be chosen as a function of the instance, or a bound on Σ_e y*_e must be proved.

minor comments (5)

[Section 3.2, Theorem 3] When stating the Chernoff–Hoeffding bound, the sentence after the choice m = n/(2δ²) should read Pr[1/m Σ W_i^e ≤ (1−w_e)−δ] ≤ 1/e^n; the displayed inequality direction in the following sentence is reversed or missing a complement.
[Section 4, Algorithm 2] Step 9 of Algorithm 2 should specify whether the deletion of pendant vertices in V_C^{<0.5} is simultaneous or iterative; the current wording leaves the structure of the resulting tree T ambiguous.
[Section 4.2] Throughout Section 4.2, the overbar notation for suffix objects (H_t^bar, V_t^bar, E_t^bar) is used inconsistently, with many formulas omitting bars in places where the proof clearly refers to the suffix. This makes the already intricate algebra extremely difficult to follow.
[Section 5, Observation 1] The notation OP T, OP T′, and OP T in Observation 1 is confusing: the first is a number of trees while the second is a weighted index. Please distinguish the two quantities notationally.
[Various] The manuscript contains numerous typographical errors, including "attibute", "Collolary", and inconsistent use of "vice" versus "vertex". A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the load-bearing bounds are derived from LP duality and structural arguments, with self-citation only as a non-load-bearing baseline.

full rationale

No circular step is present. The deterministic 2-approximation (Theorem 5) is derived from the LP relaxation, the Kruskal ordering of edges, and structural lemmas (Lemmas 6-12); the target inequality is never assumed as an input. The probabilistic 2+epsilon algorithm (Theorems 3-4) uses the binary-weight 2-approximation as a subroutine and establishes dual feasibility via Chernoff bounds; no fitted parameter is later relabeled as a prediction. The bounded forest cover 6-approximation (Theorem 6) uses the forest-cover 2-approximation plus an external edge-decomposition lemma from Khani and Salavatipour [21], and the only self-citation ([11], the authors' earlier BFC paper) supplies the problem definition and an 8-approximation baseline that is not load-bearing for the new bound. The concerns raised by the skeptic (the missing suffix analogue of inequality (26) in Lemma 8, and the treatment of y_e as fixed when computing E[y_e W_e] in Theorem 4) are correctness or rigor gaps, not circular reductions: they do not make an equation true by construction. The paper is therefore self-contained in the sense relevant to circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard LP duality, a 2-variable IP oracle, Chernoff bounds, and a structural property of the LP support. No free parameters or invented entities are introduced.

assumptions (5)

standard math Standard LP duality and weak duality for the forest cover LP and its dual.
Used throughout Section 3 and Theorem 5 to convert dual feasible solutions into lower bounds.
standard math Hochbaum-Naor polynomial-time algorithm for integer programs with two variables per inequality.
Invoked in Lemma 1 to show the separation oracle P_st is solvable in polynomial time.
standard math Chernoff-Hoeffding bound for sums of independent Bernoulli variables.
Used in Theorem 3 to show the averaged dual solution satisfies the perturbed constraints with high probability.
standard math Hall's theorem and the property that a subgraph of a tree is a forest.
Used in Lemma 12 to construct a matching saturating all low vertices in the contracted tree T'.
domain assumption Every edge in the LP support satisfies x*_u + x*_v >= 1, so at least one endpoint has x* >= 0.5; hence no edge in G* connects two vertices both below 0.5.
Load-bearing for the degree-2 claim in Lemma 12; relies on the vertex cover constraint of the LP.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Forest Covers and Bounded Forest Covers." pith.science (2026). https://pith.science/paper/HA3BDQVI

@misc{pith2026241116578,
  author       = {Pith},
  title        = {Pith review of: Forest Covers and Bounded Forest Covers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HA3BDQVI}},
  note         = {Machine review of arXiv:2411.16578}
}

abstract

We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic $2+\epsilon$ approximation algorithm for the forest cover problem is given using the method of dual fitting. A deterministic algorithm with a 2-approximation ratio that rounds the optimal solution to a linear program is given next. The 2-approximation for the forest cover is then used to give a 6-approximation for the bounded forest cover problem. The use of the probabilistic method to develop the $2+\epsilon$ approximation algorithm may be of independent interest.

Figures

Figures reproduced from arXiv: 2411.16578 by the authors.

**Figure 2.** The sub-graphs of Mh r in the sub-component S h r . Consider the graph (VSh r , EMh r ) and let Mh,1 r and Mh,2 r be two of its connected components that are connected in S h r by some edges. Let e = (i, j) ∈ ESh r be the edge with the least weight, connecting Mh,1 r and Mh,2 r , where i ∈ VMh,1 r and j ∈ VMh,2 r . Although i and j are disconnected in (VSh r , EMh r ) as e /∈ EMh r , they are still connected in M. T… view at source ↗

**Figure 3.** Partition of vertices and edges To (38), we add terms of sub-graph Ht and Ht , i.e, VD = VDt ∪ VDt , ED = EDt ∪ EDt , VT = VTt ∪ VTt , ET ≥.5 = ET ≥.5 t ∪ E T ≥.5 t , ET <.5 = ET <.5 t ∪ ET <.5 t , and ENT = ENTt ∪ ENTt . Then, the following inequality holds in a connected component C. X i∈VD x ∗ i − X (i,j)∈ED y ∗ ij (1 − wij ) + X i∈VT γi − X (i,j)∈ET≥.5 βi,j (1 − wi,j ) + X (i,j)∈ET<.5 ζi,j (1 − wi,j ) − X (i,j)∈… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 22 canonical work pages

[1]

John Wiley & Sons (2016)

Alon, N., Spencer, J.H.: The probabilistic method. John Wiley & Sons (2016)

work page 2016
[2]

Information Processing Letters 47(6), 275–282 (1993)

Arkin, E.M., Halldórsson, M.M., Hassin, R.: Approximating the tree and tour covers of a graph. Information Processing Letters 47(6), 275–282 (1993)

work page 1993
[3]

Journal of Algorithms 59(1), 1–18 (2006)

Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. Journal of Algorithms 59(1), 1–18 (2006)

work page 2006
[4]

In: 2009 24th Annual IEEE Conference on Computational Complexity

Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: 2009 24th Annual IEEE Conference on Computational Complexity. pp. 74–80. IEEE (2009)

work page 2009
[5]

In: Workshop on Algorithms and Data Structures

Berman, P., Fujito, T.: On approximation properties of the independent set problem for degree 3 graphs. In: Workshop on Algorithms and Data Structures. pp. 449–460. Springer (1995)

work page 1995
[6]

Theoretical Computer Science411(40-42), 3736–3756 (2010)

Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science411(40-42), 3736–3756 (2010)

2010
[7]

Annals of mathematics pp

Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of mathematics pp. 439–485 (2005)

2005
[8]

Theory of evolutionary computation: Recent developments in discrete optimization pp

Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. Theory of evolutionary computation: Recent developments in discrete optimization pp. 1–87 (2020)

work page 2020

Show all 27 references

[9]

Operations Research Letters 32(4), 309–315 (2004)

Even, G., Garg, N., Könemann, J., Ravi, R., Sinha, A.: Min–max tree covers of graphs. Operations Research Letters 32(4), 309–315 (2004)

2004
[10]

Networks23(1), 19–28 (1993)

Goemans, M.X., Myung, Y.S.: A catalog of steiner tree formulations. Networks23(1), 19–28 (1993)

1993
[11]

In: Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings

Gorain, B., Patra, S., Singh, R.R.: Graph covering using bounded size subgraphs. In: Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings. pp. 415–426. Springer (2023)

2023
[12]

Journal of Algorithms 24(2), 266–286 (1997)

Guttmann-Beck, N., Hassin, R.: Approximation algorithms for min–max tree partition. Journal of Algorithms 24(2), 266–286 (1997)

1997
[13]

In: SODA

Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized steiner tree problem via a new approach of primal- dual schema. In: SODA. vol. 6, pp. 631–640 (2006)

2006
[14]

Classic Papers in Combinatorics pp

Hall, P.: On representatives of subsets. Classic Papers in Combinatorics pp. 58–62 (1987)

1987
[15]

SIAM Journal on Computing31(5), 1608–1623 (2002) 27

Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing31(5), 1608–1623 (2002) 27

2002
[16]

arXiv preprint arXiv:0712.3335 (2007)

Han, Q., Punnen, A.P., Ye, Y.: A polynomial time3/2-approximation algorithm for the vertex cover problem on a class of graphs. arXiv preprint arXiv:0712.3335 (2007)

2007 arXiv
[17]

Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parameterized by solution size. In: Beyersdorff,O.,Kanté,M.M.,Kupferman,O.,Lokshtanov,D.(eds.)41stInternationalSymposiumonTheoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Fer...

2024 doi
[18]

SIAM Journal on computing 11(3), 555–556 (1982)

Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on computing 11(3), 555–556 (1982)

1982
[19]

Hochbaum, D.S., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput.23(6), 1179–1192 (1994).https://doi.org/10.1137/S0097539793251876, https: //doi.org/10.1137/S0097539793251876

1994 doi
[20]

Karp, R.: Reducibility among combinatorial problems (1972) (2021)

1972
[21]

Algorithmica69(2), 443–460 (2014)

Khani, M.R., Salavatipour, M.R.: Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica69(2), 443–460 (2014)

2014
[22]

Annals of Operations Research 18, 245–259 (1989)

Kim, T.U., Lowe, T.J., Ward, J.E., Francis, R.L.: A minimum length covering subgraph of a network. Annals of Operations Research 18, 245–259 (1989)

1989
[23]

Proceedings of the American Mathematical society7(1), 48–50 (1956)

Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society7(1), 48–50 (1956)

1956
[24]

Nguyen, V.H.: Approximating the minimum tour cover with a compact linear program. In: Advanced Compu- tational Methods for Knowledge Engineering: Proceedings of the 2nd International Conference on Computer Science, Applied Mathematics and Applications (ICCSAMA 2014). pp. 99–10...

2014
[25]

Courier Corporation (1998)

Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Courier Corporation (1998)

1998
[26]

Operations Research Letters51(5), 473–476 (2023)

Wu, J., Cheng, Y., Yang, Z., Chu, F.: A 3/2-approximation algorithm for the multiple hamiltonian path problem with no prefixed endpoints. Operations Research Letters51(5), 473–476 (2023)

2023
[27]

Theoretical Computer Science 793, 44–58 (2019) 28

Yu, W., Liu, Z., Bao, X.: New approximation algorithms for the minimum cycle cover problem. Theoretical Computer Science 793, 44–58 (2019) 28

2019

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

John Wiley & Sons (2016)

Alon, N., Spencer, J.H.: The probabilistic method. John Wiley & Sons (2016)

work page 2016

[2] [2]

Information Processing Letters 47(6), 275–282 (1993)

Arkin, E.M., Halldórsson, M.M., Hassin, R.: Approximating the tree and tour covers of a graph. Information Processing Letters 47(6), 275–282 (1993)

work page 1993

[3] [3]

Journal of Algorithms 59(1), 1–18 (2006)

Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. Journal of Algorithms 59(1), 1–18 (2006)

work page 2006

[4] [4]

In: 2009 24th Annual IEEE Conference on Computational Complexity

Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: 2009 24th Annual IEEE Conference on Computational Complexity. pp. 74–80. IEEE (2009)

work page 2009

[5] [5]

In: Workshop on Algorithms and Data Structures

Berman, P., Fujito, T.: On approximation properties of the independent set problem for degree 3 graphs. In: Workshop on Algorithms and Data Structures. pp. 449–460. Springer (1995)

work page 1995

[6] [6]

Theoretical Computer Science411(40-42), 3736–3756 (2010)

Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science411(40-42), 3736–3756 (2010)

2010

[7] [7]

Annals of mathematics pp

Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of mathematics pp. 439–485 (2005)

2005

[8] [8]

Theory of evolutionary computation: Recent developments in discrete optimization pp

Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. Theory of evolutionary computation: Recent developments in discrete optimization pp. 1–87 (2020)

work page 2020