Search

An extension of an induced path $P$ in a graph $G$ is an induced path $P'$ such that deleting the endpoints of $P'$ results in $P$. An induced path in a graph is said to be avoidable if each of its extensions is contained in an induced cycle. Beisegel, Chudovsky, Gurvich, Milanic, and Servatius (WADS 2019) conjectured that every graph that contains an induced $k$-vertex path also contains an avoidable induced path of the same length, and proved the result for $k = 2$ (the case $k = 1$ was known before). The same year Bonamy, Defrain, Hatzel, and Thiebaut proved the conjecture for all $k$. Here we strengthen their result and show that every induced path can be shifted to an avoidable one. We also prove analogous results for the non-induced case and for the case of walks, and show that the statement cannot be extended to trails or to isometric paths.

Let k be at most 0, and let X be a locally-finite CAT(k) polyhedral 2-complex X, each face with constant curvature k. Let E be a closed, rectifiably-connected subset of X with trivial first singular homology. We show that E, under the induced path metric, is a complete CAT(k) space., Comment: 13 pages, 3 figures

Let $\eta(G)$ be the number of connected induced subgraphs in a graph $G$, and $\overline{G}$ the complement of $G$. We prove that $\eta(G)+\eta(\overline{G})$ is minimum, among all $n$-vertex graphs, if and only if $G$ has no induced path on four vertices. Since the $n$-vertex tree $S_n$ with maximum degree $n-1$ is the unique tree of diameter $2$, $\eta(S_n)+\eta(\overline{S_n})$ is minimum among all $n$-vertex trees, while the maximum is shown to be achieved only by the tree whose degree sequence is $(\lceil n/2\rceil,\lfloor n/2\rfloor,1,\dots,1)$. Furthermore, we prove that every graph $G$ of order $n\geq 5$ and with maximum $\eta(G)+\eta(\overline{G})$ must have diameter at most $3$, no cut vertex and the property that $\overline{G}$ is also connected. In both cases of trees and graphs of fixed order, we find that if $\eta(G)$ is maximum then $\eta(G)+\eta(\overline{G})$ is minimum. As a corollary to our results, we characterise the unique graph $G$ of given order and number of pendent vertices, and the unique unicyclic graph $G$ of a given order that minimises $\eta(G)+\eta(\overline{G})$.

Millimetre wave (mmWave) has great potential in vehicle‐to‐vehicle (V2V) communication to provide wide bandwidth and low latency. However, the biggest challenge for the use of mmWave is the high propagation path loss and susceptibility to blockage among vehicles, especially in urban streets. Vehicle shadow fading is quite common in the actual V2V communication. The non‐line‐of‐sight scenarios are considered and the impacts of blocking vehicles on the characteristics of the V2V wireless channels are studied. The measurements are conducted for two scenarios. For the first scenario, a blocking truck is placed between transmitting and receiving cars. For the second scenario, a car is added as a reflector beside the truck. Based on the measurement results, a path loss model for the V2V communication is developed. In order to further verify the effects of building scattering, a simulation is setup and the results are consistent with the measured results.

The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertices and 493 edges and a heuristic for larger problems. Detailed computational experiments compare the results obtained by the new algorithms with other approaches in the literature and investigate the characteristics of the optimal solutions.

A cograph is a graph with no induced path on four vertices. The vicinal preorder on the vertex set of a graph is defined in terms of inclusions among the neighborhoods of vertices. The minimum number of chains with respect to the vicinal preorder required to cover the vertex set of a graph G is called the Dilworth number of G. In this paper, we prove that for a connected cograph G, the multiplicity of any distance eigenvalue except −2 and −1 is at most the Dilworth number of G. Furthermore, we show that no connected cographs have distance eigenvalues in the interval ( − 2 , − 1 ) , which generalizes a result of Lu et al. (2018) [24] .

The axiomatic study on the interval function, induced pathfunction of a connected graph is a well-known area in metric graph theory. In this paper, we present a new axiom: ( b p ) for any x , y , z ∈ V , R ( x , y ) = { x , y } ⇒ y ∈ R ( x , z ) or x ∈ R ( y , z ) . We study axiom ( b p ) on the interval function and the induced path function of a connected, simple and finite graph. We present axiomatic characterizations of the interval function of bipartite graphs and complete bipartite graphs. We extend the characterization of the interval function of bipartite graphs to arbitrary bipartite graphs including disconnected bipartite graphs. In addition, we present an axiomatic characterization of the interval function of a forest. Finally, we present an axiomatic characterization of the induced path function of a tree or a 4-cycle using the axiom ( b p ) .

A graph $G=(V,E)$ is distance hereditary if every induced path of $G$ is a shortest path. In this paper, we show that the eccentricity function $e(v)=\max\{d(v,u): u\in V\}$ in any distance-hereditary graph $G$ is almost unimodal, that is, every vertex $v$ with $e(v)> rad(G)+1$ has a neighbor with smaller eccentricity. Here, $rad(G)=\min\{e(v): v\in V\}$ is the radius of graph $G$. Moreover, we use this result to fully characterize the centers of distance-hereditary graphs. Several bounds on the eccentricity of a vertex with respect to its distance to the center of $G$ or to the ends of a diametral path are established. Finally, we propose a new linear time algorithm to compute all eccentricities in a distance-hereditary graph., 20 pages, 7 figures

Brooks’ theorem states that for a graph G, if $$\varDelta (G)\ge 3$$ , then $$\chi (G)\le \max \{\varDelta (G),\omega (G)\}$$ . Borodin and Kostochka conjectured a result strengthening Brooks’ theorem, stated as, if $$\varDelta (G)\ge 9$$ , then $$\chi (G)\le \max \{\varDelta (G)-1,\omega (G)\}$$ . This conjecture is still open for general graphs. In this paper, we show that the conjecture is true for graphs having no induced path on five vertices and no induced cycle on four vertices.

The axiomatic study on the interval function, induced path function and all-paths function of a connected graph is a well-known area in metric graph theory and related areas. In this paper, we introduce the following new axiom: (cp) v ∈ R ( u , w ) and v ∈ R ( u , x ) ⇒ w ∈ R ( v , x ) or x ∈ R ( v , w ) , for all distinct u , v , w , x ∈ V . We present characterizations of (claw, paw)-free graphs using axiom (cp) on the standard path transit functions on graphs, namely the interval function, the induced path function, and the all-paths function. We study the underlying graphs of the transit functions which are (claw, paw)-free and Hamiltonian. We present an axiomatic characterization of the interval function on (claw, paw)-free graphs. Furthermore, we obtain an axiomatic characterization of the induced path function on a subclass of (claw, paw)-free graphs.

We initialize a series of papers deepening the understanding of algorithmic properties of the width parameter maximum induced matching width (mim-width) of graphs. In this first volume we provide the first polynomial-time algorithms on graphs of bounded mim-width for problems that are not locally checkable. In particular, we give n O ( w ) -time algorithms on graphs of mim-width at most w , when given a decomposition, for the following problems: Longest Induced Path , Induced Disjoint Paths and H -Induced Topological Minor for fixed H . Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc , Permutation and Circular Permutation graphs, Convex graphs, k -Trapezoid , Circular k -Trapezoid , k -Polygon , Dilworth - k and Co- k -Degenerate graphs for fixed k . We contrast these positive results to the fact that problems about finding long non-induced paths remain hard on graphs of bounded mim-width: We show that Hamiltonian Cycle (and hence Hamiltonian Path ) is NP -hard on graphs of linear mim-width 1; this further hints at the expressive power of the mim-width parameter.

Let G be a simple graph on n vertices and J K m , G be the generalized binomial edge ideal of G in S = K [ x i , j : i ∈ [ m ] , j ∈ [ n ] ] . We give a regularity upper bound of S / J K m , G . We prove that the regularity of S / J K m , G is bounded above by n − 1 . If m ≥ n , then we show that the regularity of S / J K m , G is n − 1 . We prove that if m n , then the regularity of S / J K m , G is bounded below by max ⁡ { m − 1 , l ( G ) } , where l ( G ) is the length of longest induced path in G . Indeed, we prove Saeedi Madani-Kiani regularity upper bound conjecture for chordal graphs.

For vertices $u$ and $v$ of an $n$-vertex graph $G$, a $uv$-trail of $G$ is an induced $uv$-path of $G$ that is not a shortest $uv$-path of $G$. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in $O(n^{18})$ time, to either output a $uv$-trail of $G$ or ensure that $G$ admits no $uv$-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of $n^2\times n^2$ Boolean matrices, leading to a largely improved $O(n^{4.75})$-time algorithm., 18 pages, 6 figures, a preliminary version appeared in STACS 2022

The graph diameter, which is defined as the length of the longest shortest path in a graph, is often used to quantify graph communication properties. In particular, the graph diameter provides an intuitive measure of the worst-case pairwise distance. However, in many practical settings, where vertices can either fail or be overloaded or can be destroyed by an adversary and thus cannot be used in any communication or transportation path, it is natural to consider other possible measures of the worst-case distance. One such measure is the longest induced path. The longest induced path problem is defined as the problem of finding a subset of vertices of the largest cardinality such that the induced subgraph is a simple path. In contrast to the polynomially computable graph diameter, this problem is NP-hard. In this paper, we focus on exact solution approaches for the problem based on linear integer programming (IP) techniques. We first propose three conceptually different linear IP models and study their basic properties. To improve the performance of the standard IP solvers, we propose an exact iterative algorithm that solves a sequence of smaller IPs to obtain an optimal solution for the original problem. In addition, we develop a heuristic capable of finding induced paths in large networks. Finally, we conduct an extensive computational study to evaluate the performance of the proposed solution methods.

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path receive the same color. For a connected graph G, the proper connection number p c ( G ) of G is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of G is connected by at least one proper path in G. Recently, Li and Magnant in [8] posed the following conjecture: If G is a connected noncomplete graph of order n ≥ 5 and minimum degree δ ( G ) ≥ n / 4 , then p c ( G ) = 2 . In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if G is a connected bipartite graph of order n ≥ 4 with δ ( G ) ≥ n + 6 8 , then p c ( G ) = 2 .

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with $$\max \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} $$ many colors. If the input graph is triangle-free, we only need $$\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} $$ many colors. The running time of our algorithm is $$O((3^{t-2}+t^2)m+n)$$ if the input graph has n vertices and m edges.

Betweenness is a universal notion present in several disciplines of mathematics. The notion of betweenness has a profound history and many pioneers like Euclid, Pasch, Hilbert have studied betweenness axiomatically. In discrete mathematics too, betweenness is present and several authors have worked on this concept from an axiomatic view. In graph theory, betweenness is developed mainly as metric betweenness, studied using the shortest path metric in a connected graph, thus resulting in the notion of the interval function. Many interesting results are available in graph theory using the interval function. The interval function is generalized to induced path function by replacing shortest paths by induced paths. The induced path betweenness also captured attention among graph theorists with several interesting results to date. From an axiomatic point of view, two pertinent questions can be framed on these functions. Is it possible to axiomatically characterize the interval function of some special graphs using some set of first order axioms defined on an arbitrary transit function? Is it possible to characterize the graphs with the help of their interval functions? In this paper, we survey the results as answers to these questions available from the research papers. Keywords: Betweenness, Interval function, Induced path function

A point visibility graph is a graph induced by a set of points in the plane where the vertices of the graph represent the points in the point set and two vertices are adjacent if and only if no other point from the point set lies on the line segment between the two corresponding points. The set of all point visibility graphs form a graph class which is examined from a computational complexity perspective in this paper. We show NP-hardness for several classic graph problems on point visibility graphs such as Feedback Vertex Set , Longest Induced Path , Bisection and F - Free Vertex Deletion (for certain sets F ). Furthermore, we consider the complexity of the Dominating Set problem on point visibility graphs of points on a grid.

Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $\chi$ contains an induced cycle of length $\Omega(\chi\log\chi)$ as $\chi\to\infty$. Even if one only demands an induced path of length $\Omega(\chi\log\chi)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'., Comment: 12 pages; in v2 one section was removed due to a subtle error

Random Structures & Algorithms, 61 (4), ISSN:1042-9832, ISSN:1098-2418

For an integer $t$, a graph $G$ is called {\em{$C_{>t}$-free}} if $G$ does not contain any induced cycle on more than~$t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO$_2$ statement~$\phi$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O(\log^4 n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $\phi$. The running time can be improved to $n^{O(\log^2 n)}$ assuming $G$ is $P_t$-free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {\sc{Maximum Weight Independent Set}} problem on $P_t$-free graphs in two directions: by encompassing the more general setting of $C_{>t}$-free graphs, and by being applicable to a much wider variety of problems, such as {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}., Comment: 49 pages, 2 figures. Major changes from first (preliminary) version including changing title, adding co-authors, and significant addition to content of the paper

We show that for \(d\ge d_0({\epsilon })\), with high probability, the size of a largest induced cycle in the random graph G(n, d/n) is \((2\pm {\epsilon })\frac{n}{d}\log d\). This settles a long-standing open problem in random graph theory.

In a graph, a perfect matching cut is an edge cut that is a perfect matching. perfect matching cut (pmc) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be \(\mathsf {NP}\)-complete. We revisit the problem and show that pmc remains \(\mathsf {NP}\)-complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which pmc is polynomial time solvable. The first one includes claw-free graphs and graphs without an induced path on five vertices, the second one properly contains all chordal graphs. Assuming the Exponential Time Hypothesis, we show there is no \(O^*(2^{o(n)})\)-time algorithm for pmc even when restricted to n-vertex bipartite graphs, and also show that pmc can be solved in \(O^*(1.2721^n)\) time by means of an exact branching algorithm.

The \(kite\) and the \(dart\) are the two graphs obtained from a \(K_4-e\) by adding a vertex u and making u adjacent to one vertex of degree 2 or 3 in \(K_4-e\), respectively. The optimal \(\chi \)-binding function \(f^\star _{F_1,F_2,\ldots ,F_n}:\mathbb {N}\rightarrow \mathbb {N}\) of the class of \((F_1,F_2,\ldots ,F_n)\)-free graphs is defined by $$x\mapsto \max \{\chi (G):\omega (G)=x, G \text { is } (F_1,F_2,\ldots , F_n)\text {-free}\}.$$ In this work, we prove \(f_{P_5,kite}^\star (x)\le 2x-2\) for every \(x\ge 3\) and \(f_{P_5,dart}^\star =f_{3K_1}^\star \). In other words, we show that every \((P_5,kite)\)-free graph, say, \(G_{kite}\) with clique number at least 3 is \((2\omega (G_{kite})-2)\)-colourable and every \((P_5,dart)\)-free graph, say, \(G_{dart}\) is \(f^\star _{3K_1}(\omega (G_{dart}))\)-colourable.

Let [Formula: see text] be a graph, and let [Formula: see text] be an induced path centered at [Formula: see text]. An edge lift defined on [Formula: see text] is the action of removing edges [Formula: see text] and [Formula: see text] while adding the edge [Formula: see text] to the edge set of [Formula: see text]. In this paper, we initiate the study of the effects of edge lifting on the Roman domination number of a graph, where various properties are established. A characterization of all trees for which every edge lift increases the Roman domination number is provided. Moreover, we characterize the edge lift of a graph decreasing the Roman domination number, and we show that there are no graphs with at most one cycle for which every possible edge lift can have this property.

International audience; A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges (→B1→B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→B0→B0-VPG).In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B1B1-EPG cographs and B0B0-VPG cographs using their cotree.

Let $M_k$ be the complete, simply connected, Riemannian 2-manifold of constant curvature $k \le 0$. Let $E$ be a closed, simply connected subspace of $M_k$ with the property that every two points in $E$ is connected by a rectifiable path in $E$. We show that under the induced path metric, $E$ is a complete CAT($k$) space. We also show that the natural notions of angle coming from the intrinsic and extrinsic metrics coincide for all simple geodesic triangles., 11 pages, 5 figures; accepted for publication in Tsukuba Journal of Mathematics

Given a graph \(G=(V,E)\), the LongestInducedPath problem asks for a maximum cardinality node subset \(W\subseteq V\) such that the graph induced by W is a path. It is a long established problem with applications, e.g., in network analysis. We propose novel integer linear programming (ILP) formulations for the problem and discuss efficient implementations thereof. Comparing them with known formulations from literature, we prove that they are beneficial in theory, yielding stronger relaxations. Moreover, our experiments show their practical superiority.

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs G and H, $$G+H$$ G + H denotes the disjoint union of G and H. This manuscript shows that (i) WIS can be solved for ($$P_4+P_4$$ P 4 + P 4 , Triangle)-free graphs in polynomial time, where a $$P_4$$ P 4 is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every ($$P_4+P_4$$ P 4 + P 4 , Triangle)-free graph G there is a family $${{\mathcal {S}}}$$ S of subsets of V(G) inducing (complete) bipartite subgraphs of G, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of G is contained in some member of $${\mathcal {S}}$$ S . These results seem to be harmonic with respect to other polynomial results for WIS on [subclasses of] certain $$S_{i,j,k}$$ S i , j , k -free graphs and to other structure results on [subclasses of] Triangle-free graphs.

A compact Fuchsian manifold with boundary is a hyperbolic 3-manifold homeomorphic to $S_g \times [0; 1]$ such that the boundary component $S_g \times \{ 0\}$ is geodesic. We prove that a compact Fuchsian manifold with convex boundary is uniquely determined by the induced path metric on $S_g \times \{1\}$. We do not put further restrictions on the boundary except convexity.

Let P k denote an induced path on k vertices. For k ≥ 5 , we show that the P k -free sandwich problem, partitioned probe problem, and unpartitioned probe problem are N P -complete. For k ≤ 4 , it is known that the P k -free sandwich problem, partitioned probe problem, and unpartitioned probe problem are in P .

Many constraints on graphs, e.g. the existence of a simple path between two vertices, or the connectedness of the subgraph induced by some selection of vertices, can be straightforwardly represented by means of a suitable acyclicity constraint. One method for encoding such a constraint in terms of simple, local constraints uses a 3-valued variable for each edge, and an ( N + 1 ) -valued variable for each vertex, where N is the number of vertices in the entire graph. For graphs with many vertices, this can be somewhat inefficient in terms of space usage. In this paper, we show how to refine this encoding into one that uses only a single bit of information, i.e. a 2-valued variable, per vertex, assuming the graph in question is planar. More generally, for graphs that are embeddable in genus g (i.e. on a torus with g handles), we show that 2 g + 1 bits per vertex suffices. We furthermore show how this same constraint can be used to encode connectedness constraints, and a variety of other graph-related constraints.

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on $$P_t$$ -free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for $$t\le 5$$ (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014, pp 570–581, 2014), and an algorithm for $$t=6$$ announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on $${P}_6$$ -free graphs. CoRR, arXiv:1707.05491 , 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any $$t\ge 1$$ , there is an algorithm for Maximum Independent Set on $$P_t$$ -free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in $$2^{\mathcal {O}(\sqrt{tn \log n})}$$ time on $$P_t$$ -free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. Scattered Set is the generalization of Maximum Independent Set where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges)

Let $$\mathcal {P}(G,X)$$ be a property associating a boolean value to each pair (G, X) where G is a graph and X is a vertex subset. Assume that $$\mathcal {P}$$ is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph $$G=(V,E)$$ , find subsets $$X\subseteq F \subseteq V$$ such that the treewidth of G[F] is at most t, property $$\mathcal {P}(G[F],X)$$ is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, Independent $$\mathcal {H}$$ -Packing, etc. Fomin et al. (SIAM J Comput 44(1):54–87, 2015) proved that the problem is polynomial on the class of graph $${\mathcal {G}}_{{\text {poly}}}$$ , i.e. the graphs having at most $${\text {poly}}(n)$$ minimal separators for some polynomial $${\text {poly}}$$ . Here we consider the class $${\mathcal {G}}_{{\text {poly}}}+ kv$$ , formed by graphs of $${\mathcal {G}}_{{\text {poly}}}$$ to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on $${\mathcal {G}}_{{\text {poly}}}+ kv$$ , with parameter k, if the modulator is also part of the input.

A simple undirected graph G has the me2-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. This article considers graphs that can be embedded as induced subgraphs of me2-graphs by the introduction of additional mutually non-adjacent vertices and suitably chosen edges. The main results concern such embeddings of trees.