Pith. sign in

REVIEW 4 major objections 5 minor 24 references

Extending Simple Drawings

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

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

Pith's one-line read Extending a simple drawing by a prescribed set of missing edges is NP-complete, and maximizing the number of inserted edges is APX-hard.

desk verdict Genuinely new NP- and APX-hardness results for extending simple drawings, with the main caveat that the gadget claims rely on visual verification and one wrong citation; the paper deserves a serious referee. read the letter →

arxiv 1908.08129 v2 pith:25Q7HDZF submitted 2019-08-21 cs.CG

Alan Arroyo , Martin Derka , Irene Parada This is my paper · ORCID
classification cs.CG MSC 68Q1768U0505C1005C62
keywords simpledrawingsedgeinsertionNP-completenessAPX-hardnessgraphdrawingtopologicalgraphspathproblemwithholesdominatingset
topics P versus NP
open problems P versus NP
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

Simple drawings are graph drawings in which any two edges meet at most once, either at a shared endpoint or at a proper crossing. The paper asks when a given simple drawing of a graph can be extended by adding a prescribed set of missing edges while keeping the drawing simple. Its main result is that deciding this is NP-complete, even though the analogous question is trivial for straight-line drawings and always possible for pseudolinear drawings (those whose edges can be extended to a pseudoline arrangement). The paper also proves that choosing the largest insertable subset is APX-hard, so no polynomial-time approximation scheme exists unless P=NP, and gives a polynomial-time algorithm for inserting a single edge when its endpoints dominate the graph. The upshot is that the simple-drawing extension problem is genuinely hard in general, with only special cases admitting efficient algorithms.

What carries the argument

The load-bearing devices are three planar gadgets—the variable gadget, the clause gadget, and the wire gadget—each containing a special pair of vertices u,v whose missing edge uv has exactly one or two marked admissible insertion regions. In the NP-hardness proof, choosing the left or right region of a variable gadget records true or false; a wire gadget transmits this choice to a clause gadget and, when the literal is false, blocks the corresponding clause region by forcing any insertion to cross uv twice. For the polynomial-time single-edge result, the operative mechanism is different: the drawing is converted into a plane with at most two holes whose boundary traces the stars of u and v, and the existing edge segments become colored Jordan arcs; inserting uv is then equivalent to finding a pq-arc that crosses no color more than once. The algorithm solves this path problem with holes by enlarging holes along non-separating arcs and cutting through separating ones, reducing every relevant instance to one with a single hole.

What would settle it

Take one of the three gadgets from Fig. 2, planarize the drawing by subdividing every crossing, and test each cell of the planarized arrangement to see whether the edge uv can be drawn inside that cell without crossing any existing edge more than once. If any unmarked cell admits such an insertion, the gadget assertion used in the reduction fails, and with it the if-and-only-if between insertability of M and satisfiability of the formula.

Watch

Extended reading notes

Core claim

The central discovery is a dichotomy between easy drawing classes and arbitrary simple drawings. The paper proves that, given a simple drawing D(G) and a set M of missing edges, deciding whether M can be inserted into D(G) is NP-complete; the proof reduces monotone 3SAT to the extension problem by replacing variables, clauses, and incidences with planar gadgets whose only admissible insertion regions encode truth values and enforce clause satisfaction. Composing this with an approximation-preserving reduction from maximum independent set in cubic graphs yields that finding the largest subset of M that can be inserted is APX-hard, hence admits no polynomial-time approximation scheme unless P=NP. On the positive side, when exactly one edge uv is to be inserted and {u,v} is a dominating set (every other vertex is adjacent to u or v), the decision problem is solvable in polynomial time by reducing it to a path problem with at most two holes. These results place simple-drawing extension at a computational frontier: worst-case instances are intractable, but structured cases remain solvable.

Load-bearing premise

The whole reduction hinges on the assertion that in each gadget the edge uv can be inserted only in the marked regions, and that each wire gadget blocks its target clause region exactly as described; if a gadget admitted an unplanned insertion region, the equivalence between insertability and satisfiability would collapse.

Editorial extensions

If this is right

  • No polynomial-time algorithm can decide insertability of an arbitrary prescribed set of missing edges, unless P=NP.
  • The maximization version admits no PTAS unless P=NP, so one cannot approximate the largest insertable subset to arbitrary precision in polynomial time.
  • A single missing edge can already be uninsertable, and examples exist in drawings of K6 minus one edge and in larger complete graphs minus one edge.
  • When the endpoints of the new edge form a dominating set, single-edge insertion can be decided in polynomial time.
  • The hardness is specific to simple drawings: the corresponding extension problems are trivial for rectilinear drawings and always solvable for pseudolinear drawings.

Reading between the lines

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

  • The gadgets in the NP-hardness construction use pairwise disjoint vertex pairs for their uv edges, so the decision problem is NP-complete even when the candidate set M is a matching in the complement—a strengthening the paper does not state explicitly.
  • The single-edge algorithm's reduction to a path problem with at most two holes suggests that the difficulty of the still-open general single-edge problem may come from drawings whose planarization has many holes; testing bounded-hole classes would be a natural next step.
  • Because the reduction from maximum independent set is an L-reduction, any greedy or local-search insertion heuristic can be forced to be arbitrarily far from optimal on carefully drawn instances, so practical work would have to rely on structural restrictions or approximation schemes tailored to those restrictions.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper studies the computational complexity of extending a simple drawing D(G) of a graph G by inserting a prescribed set M of missing edges. It claims three main results: deciding whether all edges of M can be inserted into D(G) is NP-complete (Theorem 1); maximizing the number of insertable edges is APX-hard (Theorem 3 and Corollary 5); and deciding insertability of a single edge uv is polynomial-time when {u,v} is a dominating set (Theorem 7). The hardness proofs reduce from monotone 3SAT and maximum independent set in cubic graphs using variable, clause, wire, vertex, and edge gadgets. The algorithmic part reformulates single-edge insertion as a 'path problem with holes' in the planar dual and gives a polynomial-time algorithm for instances with at most two holes.

Significance. If the results are correct, they settle the complexity of a natural graph-drawing extension problem and show a sharp contrast with the rectilinear and pseudolinear settings, where extension is trivial or always possible. The paper also provides a useful dual reformulation of single-edge insertion and a nontrivial polynomial-time case. The high-level strategy is coherent and the claimed reductions are plausible. However, the hardness results rest on gadget characterizations that are asserted visually rather than proved, and the proof of Lemma 4 relies on a 'routine to check' statement. These gaps are load-bearing and must be repaired before the theorems can be considered established.

major comments (4)
  1. [Section 2, after Fig. 2 and after Fig. 4] The assertion that 'the edge uv can only be inserted in the regions where the dashed arcs are drawn' is not proved for any of the gadgets. The 'only' direction is essential: Lemma 2 and the satisfiability equivalence in Theorem 1, as well as the analogous equivalence in Section 3.1, require that no unmarked region can host uv. Because the rest of the reduction composes gadgets rigidly, a single additional feasible insertion region would permit insertions that do not correspond to a truth assignment or to an independent set, breaking the reductions. Please replace the visual assertion with a proof, for example by a case analysis of all possible positions of uv relative to the edges of each gadget, showing that every other placement forces uv to cross some edge more than once or to cross an edge incident to u or v.
  2. [Section 3.1, proof of Lemma 4] The proof states that 'It is routine to check that it is a simple drawing' for the subdrawing induced by four vertex gadgets and the corresponding edge gadgets. This is not a proof, and this check is load-bearing for the APX-hardness reduction: Theorem 3 and Corollary 5 require D'(G') to be a simple drawing. The construction in items (i)--(vi) specifies where crossings with vertex-gadget edges occur, but it does not establish that two arcs from different edge gadgets cross at most once in all configurations, nor that the interaction between an edge gadget and the two vertex gadgets is exactly as in Fig. 4c. Please provide a detailed proof, for instance by analyzing the order of crossing points along each edge of each gadget and using the 1-page book order of the original graph.
  3. [Section 2, first paragraph] The claim that the decision problem is in NP 'since it can be described combinatorially' is not sufficient. A certificate for an extension must be specified: for example, one can give the planarization of D(G) together with the rotation system of the inserted edges, and the verifier must check simplicity in polynomial time. The input representation of the simple drawing D(G) also needs to be stated explicitly. Since NP-completeness comprises membership in NP, this gap should be closed by giving the certificate and the polynomial-time verification procedure.
  4. [Section 2, Lemma 2 and construction of D'] The proof of Lemma 2 is entirely visual: the cases are argued from Fig. 3 and depend on how the wire gadget is drawn around the variable and clause gadgets. The text does not prove that, in the false case, u(W)v(W) cannot be inserted in the yellow region because it would cross u(X)v(X) twice, nor that, in the true case, the yellow insertion can always be routed. Likewise, the statement that 'Since D(φ) is a 2-page book drawing, the constructed drawing D' is a simple drawing' is asserted without proving that all wire gadgets pairwise cross at most once, both locally around vertices and globally between gadgets. Please add formal lemmas for the wire routing and for the simplicity of the global construction.
minor comments (5)
  1. [References] Reference [4] is cited as the source for the NP-completeness of monotone 3SAT, but [4] is de Berg and Khosravi's paper on optimal binary space partitions, which does not support this statement. Please cite a correct reference for monotone 3SAT.
  2. [Figures] The paper contains duplicate figure numbers: Fig. 6 and Fig. 7 appear both in Section 4 and in Appendix C, and Fig. 8 appears once in Appendix B and once in Appendix C with different content. Please renumber the figures.
  3. [Throughout] There are several typos and language errors: 'an slight abuse' should be 'a slight abuse'; 'Not that we can assume' should be 'Note that we can assume'; the proof of Lemma 4 contains 'such that such that'; and in the Conclusions, 'a pair u, v of non-adjacent edges' should be 'a pair u, v of non-adjacent vertices'.
  4. [Appendix B, proof of Theorem 6] The statement 'It is easy to see' for the equivalence between a satisfying assignment and a heterochromatic path should be expanded. The correspondence is not immediate from the figure alone, especially because the variable subgraphs use the same color for the first edge of both the positive and negative paths; please explain how the path chooses exactly one literal per variable.
  5. [Appendix C, Lemma 7] The proof of Lemma 7 refers to Fig. 8(a) and Fig. 8(b), but the cells F_p, F_q, and the arcs alpha and beta are not clearly labeled in the figures, which makes the case analysis hard to follow. Please add labels or a precise description of the cells used in the proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all hardness reductions start from external NP/APX-hard problems and the algorithmic part is developed independently.

full rationale

The paper's derivations are not circular. Theorem 1 reduces from monotone 3SAT and Theorem 3/Corollary 5 reduce from maximum independent set in cubic graphs; both are external benchmarks, not results of this paper. The gadget properties, e.g. "In each of these three gadgets shown in Fig. 2, the edge uv can only be inserted in the regions where the dashed arcs are drawn," are geometric assertions about the constructed drawings; if any were false the proof would be incorrect, but the claims are not defined in terms of the target result and do not fit parameters to data. Lemma 2 and the subsequent satisfiability equivalence use those geometric facts to build the reduction, rather than assuming the answer. The polynomial-time algorithm in Section 4 reduces the problem to the Path Problem with Holes and proves correctness via independent lemmas (e.g., Lemma 7), again without importing the target claim. No load-bearing self-citation appears: the cited work is by Kyncl, Pach, Radoicic, Toth, and other external authors, not by the present authors. The mistaken citation [4] for monotone 3SAT and the unproved visual assertion that each gadget admits only the marked insertion regions are legitimate correctness and exposition concerns, but neither is a circularity under the definitions used here.

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

The paper is proof-based, so there are no fitted parameters. The listed axioms are standard external results (NP/APX-hardness of source problems, the Caro-Wei bound) plus the domain assumption that simple drawings admit polynomial-size combinatorial certificates. The gadgets and the Path Problem with Holes are proof constructions, not invented entities with independent empirical content.

assumptions (5)
  • standard math Monotone 3SAT is NP-complete.
    Used as the source hardness problem in the proof of Theorem 1; cited to reference [4], though that reference appears to be a binary space partitions paper rather than a standard monotone 3SAT source.
  • standard math Maximum independent set is APX-hard for graphs of maximum degree at most three.
    Used to derive APX-hardness in Corollary 5; cited to Alimonti and Kann [1].
  • domain assumption Simple drawings can be represented by polynomial-size combinatorial certificates.
    Used to place the decision problem in NP in the proof of Theorem 1 ('the problem is in NP, since it can be described combinatorially'). Standard but not proved.
  • standard math Every simple graph admits a 1-page book drawing with vertices on a line and edges as circular arcs.
    Used in the construction for Lemma 4; an elementary standard fact.
  • standard math Caro-Wei bound: alpha(G) is at least the sum over vertices of 1/(d(v)+1).
    Used in Appendix A to bound |V| <= 4 alpha(G) and to establish the constants in the L-reduction proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Extending Simple Drawings." pith.science (2026). https://pith.science/paper/25Q7HDZF

@misc{pith2026190808129,
  author       = {Pith},
  title        = {Pith review of: Extending Simple Drawings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/25Q7HDZF}},
  note         = {Machine review of arXiv:1908.08129}
}
abstract

Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing $D(G)$ of a graph $G$ by inserting a set of edges from the complement of $G$ into $D(G)$ such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi's enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge $uv$ can be inserted into $D(G)$ when $\{u,v\}$ is a dominating set for the graph $G$.

Figures

Figures reproduced from arXiv: 1908.08129 by the authors.

Figure 1
Figure 1. Drawings in which the edge uv cannot be inserted. In contrast to our knowledge about Kn, little is known about simple drawings of general graphs. In [16] it was observed that, when studying simple drawings of general graphs, it is natural to try to extend them, by inserting the missing edges between non-adjacent vertices. One of the main results in this paper suggests that there is no hope for efficiently deciding w… view at source ↗
Figure 2
Figure 2. Basic gadgets for the proof of Theorem 1. 2 Inserting a given set of edges is NP-complete In this section we prove the following result: Theorem 1. Given a simple drawing D(G) of a graph G = (V, E) and a set M of edges of the complement of G, it is NP-complete to decide if D(G) can be extended with the set M. Notice first that the problem is in NP, since it can be described combinato￾rially. Our proof of Theorem 1 i… view at source ↗
Figure 3
Figure 3. Reduction from monotone 3SAT. In each of these three gadgets shown in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Basic gadgets and drawings for the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Drawing obtained by a reduction from K4 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Reduction to the path problem with holes. [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Transforming an instance of PPH: (a) enlarging a hole along an arc and [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: Reduction from 3SAT: example with four variables and three clauses. 1), where d(v) is the degree of vertex v. Thus, in our case |V | ≤ 4α. (This bound also follows from Tur´an’s theorem [22].) Plugging this into the equation obtained by the handshaking lemma we get |E|…
Figure 6
Figure 6. Figure 6: Reduction to the path problem with holes. [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: The two operations transforming an instance of the path problem with [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: Relevant figures for instances with two holes. [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 10 canonical work pages

  1. [4]

    Interna- tional Journal of Computational Geometry & Applications22(03), 187–205 (2010)

    de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. Interna- tional Journal of Computational Geometry & Applications22(03), 187–205 (2010). https://doi.org/10.1142/S0218195912500045

    doi:10.1142/s0218195912500045 2010

  2. [1]

    Theo- retical Computer Science 237(1), 123–134 (2000)

    Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theo- retical Computer Science 237(1), 123–134 (2000). https://doi.org/10.1016/S0304- 3975(98)00158-3

    doi:10.1016/s0304- 2000

  3. [2]

    ACM Transactions on Algorithms 11(4), 32:1–32:42 (2015)

    Angelini, P., Di Battista, G., Frati, F., Jel´ ınek, V., Kratochv´ ıl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. ACM Transactions on Algorithms 11(4), 32:1–32:42 (2015). https://doi.org/10.1145/2629341

    doi:10.1145/2629341 2015

  4. [3]

    Information Processing Letters 110(12-13), 521–523 (2010)

    Bagheri, A., Razzazi, M.: Planar straight-line point-set embedding of trees with partial embeddings. Information Processing Letters 110(12-13), 521–523 (2010). https://doi.org/10.1016/j.ipl.2010.04.019

    work page doi:10.1016/j.ipl.2010.04.019 2010

  5. [5]

    In: Klein, P.N

    Br¨ uckner, G., Rutter, I.: Partial and constrained level planarity. In: Klein, P.N. (ed.) Proceedings of the 28th Annual ACM-SIAM Sym- posium on Discrete Algorithms (SODA’17). pp. 2000–2011 (2017). https://doi.org/10.1137/1.9781611974782.130

    doi:10.1137/1.9781611974782.130 2017

  6. [6]

    SIAM Journal on Computing 42(5), 1803–1829 (2013)

    Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing num- ber and 1-planarity hard. SIAM Journal on Computing 42(5), 1803–1829 (2013). https://doi.org/10.1137/120872310

    doi:10.1137/120872310 2013

  7. [7]

    Journal of Computational Geometry 9(1), 213–246 (2018)

    Cardinal, J., Felsner, S.: Topological drawings of complete bipartite graphs. Journal of Computational Geometry 9(1), 213–246 (2018). https://doi.org/10.20382/jocg.v9i1a7

    work page doi:10.20382/jocg.v9i1a7 2018

  8. [8]

    Caro, Y.: New results on the independence number. Tech. rep., Tel Aviv University (1979)

    work page 1979

Show all 24 references
  1. [9]

    In: Friggstad, Z., Sack, J.R., Salavatipour, M.R

    Da Lozzo, G., Di Battista, G., Frati, F.: Extending upward planar graph drawings. In: Friggstad, Z., Sack, J.R., Salavatipour, M.R. (eds.) Proceedings of the 16th International Symposium Algorithms and Data Structures (WADS’19). pp. 339–

  2. [10]

    SIAM Journal on Comput- ing 5(4), 653–665 (1976)

    Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM Journal on Comput- ing 5(4), 653–665 (1976)

    1976

  3. [11]

    Algorithmica 41(4), 289–308 (2005)

    Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41(4), 289–308 (2005). https://doi.org/10.1007/s00453-004-1128-8

    2005 doi

  4. [12]

    Journal of Graph Algorithms and Applications 22(1), 117–138 (2018)

    Hajnal, P., Igamberdiev, A., Rote, G., Schulz, A.: Saturated simple and 2-simple topological graphs with few edges. Journal of Graph Algorithms and Applications 22(1), 117–138 (2018). https://doi.org/10.7155/jgaa.00460

    2018 doi

  5. [13]

    Computational Geometry: Theory and Applications 46(4), 466–492 (2013)

    Jel´ ınek, V., Kratochv´ ıl, J., Rutter, I.: A Kuratowski-type theorem for planarity of partially embedded graphs. Computational Geometry: Theory and Applications 46(4), 466–492 (2013). https://doi.org/10.1016/j.comgeo.2012.07.005

    2013 doi

  6. [14]

    In: Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD’15)

    Kynˇ cl, J.: Simple realizability of complete abstract topological graphs sim- plified. In: Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD’15). pp. 309–320. Springer (2015). https://doi.org/10.1007/978-3-319-27261-0 26

    2015 doi

  7. [15]

    Discrete & Com- putational Geometry 50(3), 727–770 (2013)

    Kynˇ cl, J.: Improved enumeration of simple topological graphs. Discrete & Com- putational Geometry 50(3), 727–770 (2013). https://doi.org/10.1007/s00454-013- 9535-8

    2013 doi

  8. [16]

    Computational Geometry 48(4), 295–310 (2015)

    Kynˇ cl, J., Pach, J., Radoiˇ ci´ c, R., T´ oth, G.: Saturated simple and k- simple topological graphs. Computational Geometry 48(4), 295–310 (2015). https://doi.org/10.1016/j.comgeo.2014.10.008 14 A. Arroyo et al

    2015 doi

  9. [17]

    Algorithmica 76(1), 47–67 (2015)

    Mchedlidze, T., N¨ ollenburg, M., Rutter, I.: Extending convex partial drawings of graphs. Algorithmica 76(1), 47–67 (2015). https://doi.org/10.1007/s00453-015- 0018-6

    2015 doi

  10. [18]

    Discrete & Computational Geometry 30(2), 311–320 (2003)

    Pach, J., Solymosi, J., T´ oth, G.: Unavoidable configurations in complete topo- logical graphs. Discrete & Computational Geometry 30(2), 311–320 (2003). https://doi.org/10.1007/s00454-003-0012-9

    2003 doi

  11. [19]

    Journal of Computer and System Sciences 43(3), 425–440 (1991)

    Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complex- ity classes. Journal of Computer and System Sciences 43(3), 425–440 (1991). https://doi.org/10.1016/0022-0000(91)90023-X

    1991 doi

  12. [20]

    International Journal of Foundations of Computer Science 17(5), 1061–1070 (2006)

    Patrignani, M.: On extending a partial straight-line drawing. International Journal of Foundations of Computer Science 17(5), 1061–1070 (2006). https://doi.org/10.1142/S0129054106004261

    2006 doi

  13. [21]

    Studia Scientiarum Mathematicarum Hungarica 31(4), 405–414 (1996)

    Riskin, A.: The crossing number of a cubic plane polyhedral map plus an edge. Studia Scientiarum Mathematicarum Hungarica 31(4), 405–414 (1996)

    1996

  14. [22]

    Matematikai ´ es Fizikai Lapok 48, 436–452 (1941)

    Tur´ an, P.: On an extremal problem in graph theory. Matematikai ´ es Fizikai Lapok 48, 436–452 (1941)

    1941

  15. [23]

    Wei, V.K.: A lower bound on the stability number of a simple graph. Tech. Rep. 81–11217–9, Bell Laboratories (1981) Extending Simple Drawings 15 A Proof of Corollary 5 Proof. Since the MIS problem for graphs with vertex degree at most three is APX-hard [1], it suffices to show t...

    1981

  16. [352]

    https://doi.org/10.1007/978-3-030-24766-9 25

    Springer (2019). https://doi.org/10.1007/978-3-030-24766-9 25

    2019 doi

Pith tools

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