Reducibility among NP-Hard graph problems and boundary classes

Abdul Samad; Shahid Hussain; Syed Mujtaba Hassan

REVIEW 4 major objections 5 minor 21 references

Reducibility among NP-Hard graph problems and boundary classes

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 A hereditary closed bi-reduction between two NP-hard graph problems transfers boundary classes in both directions, yielding the first boundary classes for vertex cover, clique, TSP, bounded-degree spanning tree, clique cover, and subgraph…

desk verdict A natural transfer idea undermined by a missing converse hypothesis and by applications that upgrade slice-relative boundary classes to global ones. read the letter →

arxiv 2411.14553 v2 pith:XY2PNWRR submitted 2024-11-21 cs.CC cs.CLcs.DM

Syed Mujtaba Hassan , Shahid Hussain , Abdul Samad This is my paper · ORCID

classification cs.CCcs.CLcs.DM MSC 05C8568Q17

keywords boundaryclassesNP-hardgraphproblemsreducibilitybi-reductionhereditaryindependentsetHamiltoniancycletravelingsalesperson

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

Some NP-hard graph problems become easy once the input is restricted to certain hereditary graph classes; boundary classes are the minimal remaining obstacles that keep a problem hard. This paper claims that a bi-reduction from one NP-hard graph problem to another, whose graph-to-graph part preserves hereditary classes, transfers boundary classes in both directions: $X$ is a boundary class for the source problem exactly when its image is a boundary class for the target. Applying this to known boundary classes for independent set, Hamiltonian cycle, Hamiltonian path, and vertex coloring yields the first boundary classes for vertex cover, clique, traveling salesperson, bounded-degree spanning tree, clique cover, and subgraph isomorphism. If the claim is right, any known reduction between NP-hard graph problems becomes a channel for finding the minimal hard substructures of new problems.

What carries the argument

The load-bearing device is the bi-reduction $f$ and its graph part $f_G$. A bi-reduction is a polynomial-time reduction whose restriction to a subset of the target is a bijection with a polynomial-time inverse; $f_G$ is the graph-to-graph component, obtained by discarding the parameter part of the mapping. The single condition that carries the argument is that $f_G$ is hereditary closed, meaning the image of every hereditary class is again hereditary; once that holds, boundary classes, which are intersections of descending chains of hereditary hard classes, are preserved under images and preimages. The concrete transforms used in the corollaries are the identity, complementation, the line-graph complement, and the weighted-complete-graph transform $K(\cdot)$.

What would settle it

The decisive test is on the slices the reductions actually hit: fix the spanning-tree degree bound at $2$ and solve bounded-degree spanning tree on hereditary subclasses of $Q$; if any finitely defined hereditary subclass of $Q$ is polynomial for this slice while NP-hard for Hamiltonian path, Theorem 1 rules out $Q$ as a boundary class for bounded-degree spanning tree. The same slice test applies to subgraph isomorphism with patterns restricted to complete graphs and to TSP with budget $0$.

Watch

Extended reading notes

Core claim

Theorem 3 is the paper's central claim: let $\Pi$ and $\Gamma$ be NP-hard graph problems, let $f$ be a bi-reduction from $\Pi$ to $\Gamma$, and suppose the graph reduction $f_G$ is hereditary closed. Then a hereditary class $X$ is a $(\Pi,A)$-boundary if and only if $f_G(X)$ is a $(\Gamma,f_G(A))$-boundary for some hereditary class $A \supseteq X$. The proof transfers each class in the descending chain of $\Pi$-hard classes to the image side, and uses the inverse image to rule out any strictly smaller limit class. The applications use four bi-reductions: the identity graph map with parameter change $k \mapsto n-k$ (independent set to vertex cover), complementation (independent set to clique and coloring to clique cover), the pattern map $G \mapsto (G,K_n)$ (clique to subgraph isomorphism), and the weighted-complete-graph transform $K(G)$ with budget $0$ (Hamiltonian cycle to TSP), plus the degree-bound map $G \mapsto (G,2)$ (Hamiltonian path to bounded-degree spanning tree). The paper presents the seven resulting boundary classes as the first known for these problems.

Load-bearing premise

The applications assume that a boundary class proved on a restricted slice of the target problem---patterns equal to $K_n$, tour budget $0$, or spanning-tree degree bound $2$---is automatically a boundary class for the full problem, a step the paper does not justify; the converse of Theorem 3 also silently assumes that the inverse graph reduction preserves hereditary classes.

Editorial extensions

If this is right

If Theorem 3 is correct, every hereditary-closed bi-reduction between NP-hard graph problems makes boundary classes portable, so boundary classes no longer have to be re-derived for each problem from scratch.
Seven concrete boundary classes follow: $T$ for vertex cover, $\mathrm{co}(T)$ for clique and subgraph isomorphism, $K(Q)$ and $K(R(Q))$ for traveling salesperson, $L(T)$ for clique cover, and $Q$ for bounded-degree spanning tree.
Because the transfer is an if-and-only-if, a strictly smaller limit class on either side would force one on the other side, so the theorem can also be used to certify that a candidate hereditary class is not a boundary class.
Since many NP-complete graph problems are reducible to each other, the theorem gives a general search strategy: pair a problem with a known boundary class and any known bi-reduction to another problem, and the image class is a candidate boundary class for the latter.

Reading between the lines

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

The bi-reductions in Corollaries 3, 4, 5, and 7 land in restricted slices of the target problems---patterns equal to $K_n$, tour budget $0$, and degree bound $2$---so the paper's boundary-class conclusions for subgraph isomorphism, TSP, and bounded-degree spanning tree carry an unstated assumption that hardness on those slices represents the full problem; this extension is not argued in the text.
The converse direction of Theorem 3 silently depends on the inverse graph reduction $f_G^{-1}$ preserving hereditary classes, a hypothesis that the theorem states nowhere; if that inverse closure fails, minimality can fail to transfer.
The $K(G)$ transform produces only complete graphs with $0/1$ edge weights, a highly structured slice of TSP instances; a boundary class proved on that slice may describe a thinner, potentially easier subproblem unless the slice is shown to inherit the full problem's hardness.
A natural next step would be applying the same transfer to other known boundary classes, such as those for dominating set or edge coloring, and checking whether the resulting classes remain boundary classes when the target problem is widened beyond the slice hit by the chosen reduction.

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

Short version: the transfer idea is sensible and the paper knows the right literature, but as written Theorem 3 is not proven and the corollaries overclaim. The iff in Theorem 3 needs the inverse graph reduction to preserve hereditary classes; the proof's converse silently uses that, and it is not assumed. The forward direction also has a gap: f_G(X_i) is hereditary when X_i is hereditary, which the 'hereditary closed' assumption gives, but you also need the preimage of a Γ-hard class to be a Π-hard class, and that needs the preimage to be hereditary. So the theorem currently gives at most one direction without an extra condition.

The applications then upgrade slice-relative conclusions to global boundary classes. In Corollaries 3, 4, 5, and 7, the reduction maps into a proper slice of the target: H=K_n for subgraph-isomorphism, budget k=0 for TSP, degree bound k=2 for bounded-degree-spanning-tree. Theorem 3 only yields a boundary class relative to the image container f_G(A). The minimality argument never rules out hard subclasses outside the slice. Corollary 3 is also simply wrong: G contains K_n as a subgraph iff ω(G) ≥ n, not ω(G)=n, so the reduction does not preserve the exact clique problem.

What is genuinely useful here: the general idea of transporting boundary classes through bi-reductions, and the simple observations that complement and identity reductions transfer T, co(T), L(T). The vertex-cover and clique corollaries are immediate from known equivalences, not new. The exact-version problem definitions (α(G)=k, etc.) are nonstandard and are not reconciled with the boundary-class literature, which uses the usual decision versions.

I would not send this to referees in its current form. The main theorem's missing hypothesis and the slice-relative overclaims are load-bearing; a revision that adds the inverse-heredity condition and honestly restates the corollaries as slice-relative might rescue a modest toolkit, but as it stands the central claims do not hold.

Referee Report

4 major / 5 minor

Summary. The paper defines several graph problems in an exact-value form (e.g., α(G)=k, ω(G)=k, β(G)=k) and introduces a transfer theorem (Theorem 3) for boundary classes: if Π and Γ are NP-hard graph problems and f is a bi-reduction from Π to Γ whose graph part f_G is hereditary-closed, then X is a (Π,A)-boundary class if and only if f_G(X) is a (Γ,f_G(A))-boundary class. It then applies this theorem to known boundary classes for independent-set, Hamiltonian cycle/path, and vertex-coloring, claiming seven previously unknown boundary classes for vertex-cover, clique, subgraph-isomorphism, travelling-salesperson (two classes), clique-cover, and bounded-degree-spanning-tree.

Significance. The idea of transporting boundary classes along reductions is natural and, if valid, would be a useful tool for the boundary-class literature. The paper is clearly structured and draws on a substantial body of known boundary-class results. However, the applications do not follow from the theorem as stated: the theorem only yields boundary classes relative to the image slice of the reduction, the converse direction silently assumes an inverse heredity condition, the exact-version problem definitions are unsupported and break Corollary 3, and the hereditary-class framework is not defined for weighted or two-input graph problems such as TSP and subgraph-isomorphism. The advertised results are therefore not established.

major comments (4)

[§5, Theorem 3 and Corollaries 3–7] The theorem's conclusion is only a relative statement: f_G(X) is a (Γ, f_G(A))-boundary, not an absolute boundary class for Γ. In the proof of the forward direction, after choosing a Γ-limit class Y' ⊂ f_G(X), the proof forms f_G^{-1}(Y'_i); this is legitimate only if each approximating class Y'_i lies in the image f_G(A). The definition of a Γ-limit class does not require the approximating hard classes to lie in f_G(A), and Theorem 3 gives no way to approximate an arbitrary Y' inside f_G(A). The applications ignore this: Corollary 3 maps into the slice H=K_n, Corollaries 4 and 5 map into the slice k=0, and Corollary 7 maps into the slice k=2. For example, in Corollary 7 the proof never rules out a proper hereditary subclass of Q on which bounded-degree-spanning-tree is NP-hard through instances with degree bound k=3, because those instances are outside the reduction's image. The corollaries' claims of boundary classes for the full target problems are therefore not consequences of Theorem 3.
[§5, Theorem 3 proof, converse direction] The 'if' direction requires that f_G^{-1} maps hereditary Γ-hard classes to hereditary Π-hard classes, but the theorem assumes only that f_G is hereditary-closed in the forward direction. The proof states 'as Y'_i is Γ-Hard, f_G^{-1}(Y'_i) is Π-Hard' without argument; this is precisely what must be proved. A bijective graph reduction can be hereditary-closed forward without its inverse being hereditary-closed, so the missing condition is not automatic. The corollaries do not repair this gap: they check only that removing a vertex from a graph in the specific classes T, Q, R(Q), etc. stays in the corresponding image, and none of them proves the required property for arbitrary hereditary classes and arbitrary Γ-hard classes.
[§4, Eqs. (1), (5), (6), and Corollary 3] The exact-version decision problems defined in Section 4 are nonstandard and are never shown to be NP-hard or to have the same boundary classes as the standard at-least/at-most versions cited from the literature. Corollary 3 is internally inconsistent: with clique defined by ω(G)=k in Eq. (5), the map f(⟨G,n⟩)=⟨G,K_n⟩ sends a no-instance ⟨G,n⟩ with ω(G)>n to a yes-instance of subgraph-isomorphism, so f is not a reduction, let alone a bi-reduction, from the paper's clique problem. The same unsupported exact-version issue affects Corollaries 1 and 2, where the known boundary class T for independent-set is transferred without any argument that it is a boundary class for the equality version α(G)=k.
[§4 and §5.1, applications to TSP and subgraph-isomorphism] The boundary-class framework is defined in Section 2 only for unweighted graphs, but the applications to travelling-salesperson and subgraph-isomorphism use inputs that are outside this framework. K(G) is a weighted complete graph, yet the paper never defines induced subgraphs or hereditary classes for weighted graphs; subgraph-isomorphism instances are pairs (G,H), and the graph reduction f_G transforms only the first coordinate, leaving the meaning of f_G(X), of a hereditary class of pairs, and of a Γ-hard class for subgraph-isomorphism unspecified. Without these definitions, Theorem 3 cannot be applied to these problems, and the claims in Corollaries 3–5 are not checkable.

minor comments (5)

[§5.1, paragraph after Figure 3] The sentence 'The inverse L^{-1}(X)' is incomplete; the inverse line-graph transformation is never defined.
[Corollary 5] The final sentence says 'by Theorem 3, K(Q) is a boundary class for traveling-saleperson', but the intended conclusion concerns K(R(Q)); the spelling 'traveling-saleperson' also appears in Corollaries 4 and 5 and should be corrected.
[§3, definition of Y-limit class] The phrase 'a Y-limit class ... of Y' is not formally defined; the definition should state explicitly that each approximating class X_i is a hereditary subclass of Y.
[Abstract and Conclusion] The paper asserts that the obtained classes are 'previously unknown' and are the first boundary classes for vertex-cover, clique, TSP, bounded-degree-spanning-tree, clique-cover, and subgraph-isomorphism, but no literature survey supports the 'first' claim; it should be supported or qualified.
[Corollary 7 proof] The reduction from Hamiltonian path to bounded-degree-spanning-tree is cited only to [7]; a more specific citation, e.g., to the relevant theorem or problem number in that book, would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the transfer theorem is a conditional result built on externally established boundary classes; the absolute-vs-relative overclaim is a correctness gap, not circular reasoning.

full rationale

The paper's derivation chain is conditional. Theorem 3 states a general transfer principle for boundary classes under bi-reductions, and its proof is a direct minimality argument rather than a restatement of its conclusion. The input boundary classes (T for independent-set, Q and R(Q) for Hamiltonian cycle, co(L(T)) for vertex-coloring, Q for Hamiltonian path) are taken from external literature: Alekseev, Korpelainen et al., Malyshev, and Munaro. These are independent sources, not the paper's own fitted values or a self-citation chain. The only self-citation, reference [1] (AbouEisha, Hussain, Lozin, Monnot, Ries, Zamaraev), appears in the introduction as one listed example of a known boundary class and is not load-bearing for any theorem or corollary. The seven corollaries compute images of these external boundary classes under explicit bi-reductions; the fact that the output class is f_G(X) by construction is exactly what a transfer theorem is meant to establish, and the theorem supplies the needed minimality argument. There is a genuine correctness gap: Theorem 3 yields at most a (Γ, f_G(A))-boundary, while Corollaries 3, 4, 5, and 7 assert absolute boundary classes for the full target problems even though the reductions are bijections onto proper slices (H=K_n, budget k=0, degree bound k=2). That is an unjustified extension, and the proof of the converse direction silently assumes the inverse graph reduction behaves well on all Γ-hard classes. However, this is a soundness or overclaim problem, not circularity: the conclusion is not being used as an input, and no fitted parameter is renamed as a prediction. No circular step can be exhibited from the paper's own equations or definitions, so the appropriate finding is no significant circularity.

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

The paper introduces no new entities or fitted parameters. Its load-bearing premises are the nonstandard exact-version problem definitions, the ill-supported converse of the transfer theorem, and the assumption that restricted boundary classes imply full-problem boundary classes.

assumptions (4)

ad hoc to paper Exact-version decision problems alpha(G)=k, omega(G)=k, beta(G)=k are NP-hard and share the boundary classes of the standard at-least/at-most versions.
Section 4 defines these nonstandard exact versions and Section 5.1 applies boundary classes from [2],[3] proved for the maximum independent set problem without justification.
ad hoc to paper The graph reduction being hereditary-closed in the forward direction is sufficient for the if-and-only-if boundary class transfer.
The converse proof (Section 5, proof of Theorem 3) uses preimages f_G^{-1}(Y'_i) as hereditary Pi-hard classes, but the theorem only assumes f_G preserves heredity forward.
ad hoc to paper A boundary class for Gamma with respect to the subclass f_G(A) of the reduction image is a boundary class for the full problem Gamma.
Corollaries 3, 4, 5, 7 conclude global boundary classes although the reductions map into proper subsets of Gamma instances.
standard math Standard NP-hardness framework and prior boundary class results of Alekseev et al. [2],[3], Korpelainen et al. [10], Malyshev [12], and Munaro [18].
These are background results the paper relies on; they are standard in the field.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Reducibility among NP-Hard graph problems and boundary classes." pith.science (2026). https://pith.science/paper/XY2PNWRR

@misc{pith2026241114553,
  author       = {Pith},
  title        = {Pith review of: Reducibility among NP-Hard graph problems and boundary classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XY2PNWRR}},
  note         = {Machine review of arXiv:2411.14553}
}

read the original abstract

Many NP-hard graph problems become easy for some classes of graphs. For example, coloring is easy for bipartite graphs, but NP-hard in general. So we can ask question like when does a hard problem become easy? What is the minimum substructure for which the problem remains hard? We use the notion of boundary classes to study such questions. In this paper, we introduce a method for transforming the boundary class of one NP-hard graph problem into a boundary class for another problem. If {\Pi} and {\Gamma} are two NP-hard graph problems where {\Pi} is reducible to {\Gamma}, we transform a boundary class of {\Pi} into a boundary class of {\Gamma}. More formally if {\Pi} is reducible to {\Gamma}, where the reduction satisfies certain conditions, then X is a boundary class of {\Pi} if and only if the image of X under the reduction is a boundary class of {\Gamma}. This gives us a relationship between boundary classes and reducibility among several NP-hard problems. To show the strength of our main result, we apply our theorem to obtain some previously unknown boundary classes for a few graph problems namely; vertex-cover, clique, traveling-salesperson, bounded-degree-spanning-tree, subgraph-isomorphism and clique-cover.

Figures

Figures reproduced from arXiv: 2411.14553 by the authors.

**Figure 2.** A caterpillar with hair of arbitrary length for some [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** An example of the line graph transformation [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Example of transformation R(G) Proof. Since T is a boundary class for independent-set. For a graph G = (V, E) we have that α(G) = ω(co(G)) (see [21]). So we have that the function f ∶ Σ ∗ → Σ ∗ , such that f(⟨G, k⟩) = ⟨co(G), k⟩ is a bireduction from independent-set t…

**Figure 5.** Figure 5: An example of the complement transformation [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: An example of the complete graph transformation [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages

[1]

A boundary property for upper domination

Hassan AbouEisha, Shahid Hussain, Vadim Lozin, Jerome Monnot, Bernard Ries, and Viktor Zamaraev. A boundary property for upper domination. In Veli M¨ akinen, Simon J. Puglisi, and Leena Salmela, editors, Combinatorial Algorithms, pages 229–240, Cham, 2016. Springer International Publishing

work page 2016
[2]

On easy and hard hereditary classes of graphs with respect to the independent set problem

Vladimir Alekseev. On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Applied Mathematics , 132(1-3):17–26, 2003

work page 2003
[3]

NP-hard graph problems and boundary classes of graphs

Vladimir Alekseev, Rodica Boliac, Dmitry Korobitsyn, and Vadim Lozin. NP-hard graph problems and boundary classes of graphs. Theoretical Computer Science, 389(1-2):219–236, 2007

work page 2007
[4]

Boundary classes of graphs for the dominating set problem

Vladimir Alekseev, Dmitry Korobitsyn, and Vadim Lozin. Boundary classes of graphs for the dominating set problem. Discrete Mathematics, 285(1):1–6, 2004

work page 2004
[5]

On the complexity of the dominating induced matching problem in hereditary classes of graphs

Domingos Cardoso, Nicholas Korpelainen, and Vadim Lozin. On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Mathematics , 159(7):521– 531, 2011. Graphs, Algorithms, and Their Applications — in Honor of Martin Charles Golumbic on the Occasion of His 60th Birthday

work page 2011
[6]

G. S. Dakhno and Dmitriy Malyshev. On a countable family of boundary graph classes for the dominating set problem. Journal of Applied and Industrial Mathematics , 17(1):25–31, Mar 2023. 8 SM. Hassan et al. Reducibility among NP-Hard graph problems and boundary classes

work page 2023
[7]

Computers and Intractability; A Guide to the Theory of NP- Completeness

Michael Garey and David Johnson. Computers and Intractability; A Guide to the Theory of NP- Completeness. W. H. Freeman & Co., USA, 1990

work page 1990
[8]

Reducibility among combinatorial problems

Richard Manning Karp. Reducibility among combinatorial problems. Proceedings of a symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York., 1972

work page 1972

Show all 21 references

[9]

A boundary class for the k-path partition problem

Nicholas Korpelainen. A boundary class for the k-path partition problem. Electronic Notes in Discrete Mathematics, 67:49–56, 2018. TREPAM 2017: Recent Trends in Pure and Applied Mathematics

2018
[10]

Boundary properties of graphs for algorithmic graph problems

Nicholas Korpelainen, Vadim Lozin, Dmitriy Malyshev, and Alexander Tiskin. Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, 412(29):3545–3554, 2011

2011
[11]

Hamiltonian cycles in subcubic graphs: What makes the problem difficult

Nicholas Korpelainen, Vadim Lozin, and Alexander Tiskin. Hamiltonian cycles in subcubic graphs: What makes the problem difficult. volume 6108, pages 320–327, 06 2010

2010
[12]

On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number

Dmitriy Malyshev. On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number. Discrete Mathematics and Applications , 21(5- 6):645–649, 2011

2011
[13]

A study of the boundary graph classes for colorability problems

Dmitriy Malyshev. A study of the boundary graph classes for colorability problems. Journal of Applied and Industrial Mathematics , 7, 04 2013

2013
[14]

Boundary graph classes for some maximum induced subgraph problems

Dmitriy Malyshev. Boundary graph classes for some maximum induced subgraph problems. Journal of Combinatorial Optimization , 27, 02 2014

2014
[15]

Classes of graphs critical for the edge list-ranking problem

Dmitriy Malyshev. Classes of graphs critical for the edge list-ranking problem. Journal of Applied and Industrial Mathematics , 8:245–255, 04 2014

2014
[16]

The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices

Dmitriy Malyshev. The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices. Siberian Electronic Mathematical Reports, 11:811–822, 01 2014

2014
[17]

A complexity dichotomy and a new boundary class for the dominating set problem

Dmitriy Malyshev. A complexity dichotomy and a new boundary class for the dominating set problem. Journal of Combinatorial Optimization , 32(1):226–243, 2016

2016
[18]

Boundary classes for graph problems involving non-local properties

Andrea Munaro. Boundary classes for graph problems involving non-local properties. Theoretical Com- puter Science, 692:46–71, 2017

2017
[19]

Role colouring graphs in hereditary classes

Christopher Purcell and Puck Rombach. Role colouring graphs in hereditary classes. Theoretical Com- puter Science, 876:12–24, 2021

2021
[20]

Introduction to the Theory of Computation

Michael Sipser. Introduction to the Theory of Computation . Course Technology, Boston, MA, third edition, 2013

2013
[21]

Introduction to Graph Theory

Douglas Brent West. Introduction to Graph Theory. Prentice Hall, 2001. 9

2001

Pith tools

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

[1] [1]

A boundary property for upper domination

Hassan AbouEisha, Shahid Hussain, Vadim Lozin, Jerome Monnot, Bernard Ries, and Viktor Zamaraev. A boundary property for upper domination. In Veli M¨ akinen, Simon J. Puglisi, and Leena Salmela, editors, Combinatorial Algorithms, pages 229–240, Cham, 2016. Springer International Publishing

work page 2016

[2] [2]

On easy and hard hereditary classes of graphs with respect to the independent set problem

Vladimir Alekseev. On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Applied Mathematics , 132(1-3):17–26, 2003

work page 2003

[3] [3]

NP-hard graph problems and boundary classes of graphs

Vladimir Alekseev, Rodica Boliac, Dmitry Korobitsyn, and Vadim Lozin. NP-hard graph problems and boundary classes of graphs. Theoretical Computer Science, 389(1-2):219–236, 2007

work page 2007

[4] [4]

Boundary classes of graphs for the dominating set problem

Vladimir Alekseev, Dmitry Korobitsyn, and Vadim Lozin. Boundary classes of graphs for the dominating set problem. Discrete Mathematics, 285(1):1–6, 2004

work page 2004

[5] [5]

On the complexity of the dominating induced matching problem in hereditary classes of graphs

Domingos Cardoso, Nicholas Korpelainen, and Vadim Lozin. On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Mathematics , 159(7):521– 531, 2011. Graphs, Algorithms, and Their Applications — in Honor of Martin Charles Golumbic on the Occasion of His 60th Birthday

work page 2011

[6] [6]

G. S. Dakhno and Dmitriy Malyshev. On a countable family of boundary graph classes for the dominating set problem. Journal of Applied and Industrial Mathematics , 17(1):25–31, Mar 2023. 8 SM. Hassan et al. Reducibility among NP-Hard graph problems and boundary classes

work page 2023

[7] [7]

Computers and Intractability; A Guide to the Theory of NP- Completeness

Michael Garey and David Johnson. Computers and Intractability; A Guide to the Theory of NP- Completeness. W. H. Freeman & Co., USA, 1990

work page 1990

[8] [8]

Reducibility among combinatorial problems

Richard Manning Karp. Reducibility among combinatorial problems. Proceedings of a symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York., 1972

work page 1972