domain: sdv shs

text:
Kamel Alhanout

Sok-Siya Bun

Karine Retornaz

Laurent Chiche

Nathalie Colombini
email: nathalie.colombini@ap-hm.fr

Prescription errors related to the use of computerized provider order-entry system for pediatric patients

Keywords: Drug Prescriptions, Medical order entry systems, Pediatrics, Medication errors

Introduction

Medication errors are a major source of risk and injury to patients, especially pediatric patients [START_REF] Engum | An evaluation of medication errors-the pediatric surgical service experience[END_REF][START_REF] Stultz | Prescription order risk factors for pediatric dosing alerts[END_REF]. The disadvantages of handwritten orders include illegibility, the timeconsuming process for pharmacy approval, and an absence of immediate notification systems regarding drug interactions and misuse [START_REF] King | The effect of computerized physician order entry on medication errors and adverse drug events in pediatric inpatients[END_REF][START_REF] Goldman | Beyond the basics: Refills by electronic prescribing[END_REF]. Hence, the replacement of handwritten orders by the computerized provider order-entry (CPOE) system is increasingly used in hospitals and health-care centers [START_REF] Arques-Armoiry | Most frequent drug-related events detected by pharmacists during prescription analysis in a University Hospital[END_REF][START_REF] Eslami | The impact of computerized physician medication order entry in hospitalized patients-A systematic review[END_REF]. Indeed, the use of CPOE provides undisputable advantages, such as the elimination of illegibility problems and the ability to include notification systems that assist in the prescription process [START_REF] Holdsworth | Impact of computerized prescriber order entry on the incidence of adverse drug events in pediatric inpatients[END_REF]. Nevertheless, data regarding errors resulting from CPOE are frequently reported, especially when the system is initially implemented [START_REF] Schwartzberg | We thought we would be perfect: medication errors before and after the initiation of Computerized Physician Order Entry[END_REF][START_REF] Samaranayake | Technology-related medication errors in a tertiary hospital: A 5-year analysis of reported medication incidents[END_REF]. Moreover, it has been noted that these errors can occur at any stage within the therapy management, including prescribing, dispensing, administering, and monitoring [START_REF] Schwartzberg | We thought we would be perfect: medication errors before and after the initiation of Computerized Physician Order Entry[END_REF]. The reasons behind such errors are in part due to various technical reasons such as confusing software, a screen overload as well as human-related issues such as lack of experience and training, cognitive overload or depersonalization between healthcare actors, as face to face communication is replaced by computer accessibility [START_REF] Hellot-Guersing | Erreurs médicamenteuses induites par l'informatisation de la prescription à l'hôpital : recueil et analyse sur une période de 4 ans[END_REF][START_REF] Malbranche | La sécurisation par l'informatisation des prescriptions : les médicaments administrés sont-ils ceux prescrits ?[END_REF]. During the last decade, errors resulting from recently implemented CPOE systems have been reported in many worldwide studies, including France [START_REF] Hellot-Guersing | Erreurs médicamenteuses induites par l'informatisation de la prescription à l'hôpital : recueil et analyse sur une période de 4 ans[END_REF][START_REF] Malbranche | La sécurisation par l'informatisation des prescriptions : les médicaments administrés sont-ils ceux prescrits ?[END_REF][START_REF] Chapman | Implementation of computerized provider order entry in a neonatal intensive care unit: Impact on admission workflow[END_REF][START_REF] Reynolds | Alerting strategies in computerized physician order entry: a novel use of a dashboard-style analytics tool in a children's hospital[END_REF]. Our study focused on the errors that occur when CPOE is used to prescribe drugs to pediatric patients. Hence, we researched and noted all pharmacist interventions (PharmInts) that involved different errors in prescriptions for pediatric patients over a 6-month period. The nature and frequency of these errors, and the drugs concerned noted in the PharmInt, were analyzed to evaluate the efficiency of the CPOE systems for pediatric use.

Methods

We performed a retrospective study that noted errors related to computerized orders carried out by the software Pharma® (Computer Engineering, France) in pediatric department between 31/05/2015 and 01/12/2015. Pharma® computerizes various steps within the therapy management, including prescription, pharmaceutical approval, and administration by the nursing staff. Interestingly, this CPOE system allows prescribers, pharmacists, and nursing staff to share notices, opinions, and various decisions on interventions.

Prescribers are trained periodically after the implementation of CPOE in clinical departments.

These training courses are offered but not imposed, to all prescribers every 6 months. A total of 924 patients were admitted into the pediatric department and registered into Pharma® during the study period. The patients' characteristics are presented in Figure 1. Prescriptions are made informatically by prescribers using Pharma®. Each patient has an account that is created by the hospital entry office where information such as the patient's name and age are found. When physicians prescribe, they must mention patient's bodyweight and choose appropriate medications. Prescribers then choose those medications from the list of drugs proposed by the CPOE software.

Clinical pharmacists who use CPOE daily gave their approval when no prescription errors were found. In other cases, clinical pharmacists realized a PharmInt that needed to be read by the prescriber and/or nursing staff. Such a PharmInt was formulated as a "Memo" when it concerned a general remark, such as in the case of the absence of a patient's bodyweight.

The PharmInt could also be formulated as a pharmaceutical opinion related to the prescribed drug. The pharmaceutical opinions were evaluated and then validated by the prescriber(s).

When necessary, pharmacists could suspend drug delivery or request modifications of a prescription with the prescriber(s) consent.

Results

A total of 1297 computerized orders containing 4722 prescriptions were assessed by the pediatric department. From these prescriptions, a total of 302 pharmacist interventions (PharmInts) were carried out by clinical pharmacists (6.4%, Table 1, Figure 2). Of the 302 PharmInts, a total of 95 (31.5%) contained no data on the patient's bodyweight, which should have been provided by the prescriber (Table 1). After the PharmInt, information on bodyweight was then provided in 47 of these cases (15.6%); however, in the other 48 cases (15.9%), the information on bodyweight was never provided despite the PharmInt.

Errors related to administration frequency of drugs such as paracetamol and phloroglucinol prescribed as to be "used when needed", accounted for 19.9% of total PharmInts (Table 1).

For example, if physicians prescribe only 4 times daily without mentioning the precise interval, it is considered as a frequency administration error by the pharmacist. Prescribing an excessive dose occurred in 17.6% of PharmInts, inappropriate modifications of prescription unit accounted for 9.9% of PharmInts and incorrect dosage form for 8.3% of PharmInts (Table 1). PharmInts that highlighted the prescription of a contraindicated drug, the need for treatment monitoring, and/or the risk of a drug-drug interaction accounted for 4%, 3.3%, and 3.3 % of PharmInts, respectively (Table 1). Errors relating to incorrect dosing regimens and an absence of treatment duration were found in 1.3% and 1% of total PharmInts, respectively (Table 1).

Of the 302 PharmInts, 255 concerned prescription errors and bodyweight missing not provided after PharmInt. Table 2 lists the drugs that were subject to 255 PharmInts and the errors associated with their prescriptions. Paracetamol (in its different forms: injectable, solid or liquid oral forms) was the main drug concerned and accounted for 36.3% of total PharmInts. Noted errors for this drug included an incorrect dosage form, co-administration of two paracetamol-containing drugs, modification of a prescription unit, errors in the frequency of administrations, or the absence of bodyweight data. Phloroglucinol and esomeprazole that appeared in PharmInts were mainly related to modifications to the prescription unit and inconsistent dosages. Notably, drugs presented in liquid oral forms, such as antibiotics or antipyretics, were frequently prescribed with modified prescription units. This was exemplified by paracetamol, which is habitually prescribed in dose-kg mode whereas some prescribers changed this to milliliter or milligram mode. This was also noted within two prescriptions for dalteparine, where prescribers used "UI anti-Xa" instead of "syringe", inserting a dose of 1 UI anti-Xa/day in the prescription instead of 1 syringe/day (each syringe contains 2500 UI anti-Xa). As noted in Table 2, inconsistent use of contradicted or non-used drugs for pediatric patients was noted for drugs such as ketoprofene (Profenid®, Bi-profenid®), dorzolamide /timolol eye drops (Cosopt®), Saccharomyces boulardii (Ultralevure®), dexamethasone/oxytetracycline (Sterdex®), and trimebutine (Debridat®). The prescription of inadequate dosage to pediatric patients, such as injectable paracetamol 1000 mg/100 mL instead of 500 mg/50 mL, or injectable methylprednisolone 120 mg, were also observed and the prescriber was notified. It should be noted that 52 of the 302 PharmInts (17.2%) had no response (validation or non-validation of notification) from the prescriber.

Discussion

Various studies have highlighted the risk of CPOE to produce errors that may be lifethreatening for patients [START_REF] Stultz | Prescription order risk factors for pediatric dosing alerts[END_REF][START_REF] Han | Unexpected increased mortality after implementation of a commercially sold computerized physician order entry system[END_REF][START_REF] Jones | Implementing computerized prescriber order entry in a children's hospital[END_REF][START_REF] Nerich | Computerized physician order entry of injectable antineoplastic drugs: An epidemiologic study of prescribing medication errors[END_REF]. Thus, each healthcare center using a CPOE system must be aware of this situation [START_REF] Schwartzberg | We thought we would be perfect: medication errors before and after the initiation of Computerized Physician Order Entry[END_REF][START_REF] Hellot-Guersing | Erreurs médicamenteuses induites par l'informatisation de la prescription à l'hôpital : recueil et analyse sur une période de 4 ans[END_REF][START_REF] Bates | Preventing medication errors: a summary[END_REF][START_REF] Balasuriya | Computerized Dose Range Checking Using Hard and Soft Stop Alerts Reduces Prescribing Errors in a Pediatric Intensive Care Unit[END_REF][START_REF] Cl | A systematic review of the types and causes of prescribing errors generated from using computerized provider order entry systems in primary and secondary care[END_REF][START_REF] Prgomet | Impact of commercial computerized provider order entry (CPOE) and clinical decision support systems (CDSSs) on medication errors, length of stay, and mortality in intensive care units: a systematic review and meta-analysis[END_REF]. Our study focused only on errors that were encountered when using CPOE to manage pediatric patients.

It should be noted that the lack of information regarding pediatric bodyweight was the most frequent error and was the main cause for a PharmInt in our study. Information on bodyweight is crucial for checking accurate drug dosages [START_REF] Jones | Implementing computerized prescriber order entry in a children's hospital[END_REF]. However, because bodyweight information is not mandatory when completing prescriptions via the CPOE system, clinicians often prescribe despite the absence of a patient's weight. Pharmacists usually notify the absence of bodyweight data and will indicate this on the Pharma® database, as well as making phone contact to approve the prescription. Consequently, data on bodyweight may be included later, although this is not always the case. The process of supplementing data is time consuming and reduces the advantages of using CPOE. This problem could be resolved by the software designer who could make it mandatory to provide information on a patient's bodyweight before a prescription can be filled. Prescribers would then be aware of this absence before pharmacy approval and thus be able to eliminate this problem.

In our study, errors related to paracetamol prescriptions were recurrent as it is frequently prescribed to children. Although it might seem insignificant to prescribers, errors in administration frequency might be problematic as it can expose the patient to an overdose that can be highly toxic to pediatric patients [START_REF] Ji Westbrook | Stepped-wedge cluster randomised controlled trial to assess the effectiveness of an electronic medication management system to reduce medication errors, adverse drug events and average length of stay at two paediatric hospitals: a study protocol[END_REF][START_REF] De Giorgi | Risk and pharmacoeconomic analyses of the injectable medication process in the paediatric and neonatal intensive care units[END_REF]. Moreover, some drugs, such as paracetamol or phloroglucinol, are prescribed under the notice of "when needed". In these conditions, when information about time intervals between doses is absent, errors may occur, such as administrating the total dose (per day) all at once, and thus exposing the patient to toxic levels [START_REF] De Giorgi | Risk and pharmacoeconomic analyses of the injectable medication process in the paediatric and neonatal intensive care units[END_REF]. Other errors, such as an incorrect drug name or dose are potentially dangerous to all patients, but particularly when they are pediatric patients [START_REF] Holdsworth | Impact of computerized prescriber order entry on the incidence of adverse drug events in pediatric inpatients[END_REF][START_REF] Prgomet | Impact of commercial computerized provider order entry (CPOE) and clinical decision support systems (CDSSs) on medication errors, length of stay, and mortality in intensive care units: a systematic review and meta-analysis[END_REF].

As reported previously, these errors can occur when the prescriber chooses an incorrect drug from the list of drugs proposed by the CPOE software, which calls for prescribers, pharmacists, and nursing personnel to be more attentive [START_REF] Engum | An evaluation of medication errors-the pediatric surgical service experience[END_REF][START_REF] Stultz | Prescription order risk factors for pediatric dosing alerts[END_REF][START_REF] Arques-Armoiry | Most frequent drug-related events detected by pharmacists during prescription analysis in a University Hospital[END_REF][START_REF] Cl | A systematic review of the types and causes of prescribing errors generated from using computerized provider order entry systems in primary and secondary care[END_REF]. In our study, clinical pharmacists detected and informed the prescriber of errors using Pharma® via PharmInt which was either validated or not by the prescriber. However, as previously noted, many PharmInts that had an error were left without a response from the prescriber. Thus, pharmacists frequently need to phone or make personal contact with the prescriber before validation of a questionable prescription. This reduces the benefits of the CPOE, which is to enable more rapid and efficient communication between health-care actors and is fundamental in optimizing healthcare management [START_REF] Engum | An evaluation of medication errors-the pediatric surgical service experience[END_REF][START_REF] Arques-Armoiry | Most frequent drug-related events detected by pharmacists during prescription analysis in a University Hospital[END_REF][START_REF] Ji Westbrook | Stepped-wedge cluster randomised controlled trial to assess the effectiveness of an electronic medication management system to reduce medication errors, adverse drug events and average length of stay at two paediatric hospitals: a study protocol[END_REF].

Modification of the prescription unit has also been reported to be one of the CPOE errors [START_REF] Hellot-Guersing | Erreurs médicamenteuses induites par l'informatisation de la prescription à l'hôpital : recueil et analyse sur une période de 4 ans[END_REF]. In our study, we noted 30 cases of inappropriate modification prescription unit which could lead to potential errors of administrations. For example, Dalteparine should be prescribed either 2500 UI anti-Xa/administration or 1 syringe/administration according to hospital recommendations. In Pharma®, "syringe" is the unit as the default of dalteparine. In two cases, "syringe" was modified by prescriber to "UI anti-Xa", which led to a dose of 1 UI anti-Xa instead of 2500 UI anti-Xa.

Conclusion

We have researched the use of a CPOE in France, specifically with regards to pediatric patients as they are particularly vulnerable to medical errors.

Our work revealed several error types in prescribing for pediatric patients, mainly absence of bodyweight, incorrect frequency of administration and excessive doses. The role of better software design is pivotal to avoiding these errors. Consequently, we decided to make it mandatory to provide bodyweight data on the Pharma® form.

In addition to optimizing the quality of CPOE-entries, well-designed software, better-trained users, and improved communication among healthcare will reduce errors.

Clinician pharmacists should have a key role in education prescribers to respect the required parameters and to elaborate computerized pediatric protocols.

Finally, communication between healthcare actors can be improved by using CPOE system tools, such as comments, and notes. These interventions can be rapidly shared when using this computerized method, and allowed to secure the ordering system and to improve the quality of healthcare management. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. Color should be used for figure 2

in print

Figure 1 :

 1 Figure 1: Characteristics of patients admitted into the pediatric department and registered into Pharma® during the study period.

Figure 2 :

 2 Figure 2: Frequency of pharmacist interventions regarding errors encountered on the computerized prescriptions.

4 )

 4 Omeprazole 10 mg tablets (Mopral) Incorrect dosage form 1 (0.4) Trimébutine 50 mg/5 mL injectable solution (non-proprietary name, PharmInt: pharmacist intervention

Table 1 :

 1 Total pharmacist interventions regarding errors encountered on the computerized prescriptions. Bodyweight was supplied to Pharma® due to the PharmInt, b: bodyweight was never supplied to Pharma®, despite the PharmInt

	Subject of PharmInt	Frequency of PharmInts (%)
	Incorrect Frequency administration	60 (19.9)
	Excessive dose		53 (17.6)
	No weight available	a	47 (15.6)
	No weight available	b	48 (15.9)
	Inappropriate modification of prescription unit	30 (9.9)
	Incorrect dosage form	25 (8.3)
	Prescription of a contraindicated drug	12 (4.0)
	Need for treatment monitoring	10 (3.3)
	Presence of drug-drug interaction	10 (3.3)
	Wrong dosing regimen	4 (1.3)
	Absence of treatment duration	3 (1.0)
	Total		302 (100)
	PharmInt : Pharmacist intervention
	a:

Table 2 :

 2 Pharmacist interventions and errors encountered with the prescribed drugs.

	INN (commercial name)	Errors


Alexandre Dolgui
email: alexandre.dolgui@imt-atlantique.fr

Mikhail Y Kovalyov
email: kovalyovmy@newman.bas-net.by

Alexander Dolgui

Alain Quilliot
email: alain.quilliot@isima.fr

Simple Paths with Exact and Forbidden Lengths

Keywords: shortest path problem, longest path problem, exact path length, forbidden path length, computational complexity, approximation

come

Introduction

Let G = (V, A) be an arbitrary arc weighted directed multigraph, which we further call graph and where V = {1, . . . , n} is the set of vertices and A is the set of arcs, |A| = m. Arc a (r) ij ∈ A is defined by its head vertex i ∈ V , tail vertex j ∈ V and its copy marker r, if there are several arcs with the same head and the same tail. A length l(a), which is an arbitrary integer number, is associated with each arc a ∈ A, and the length L(P ) of a path P from one specified vertex of G to another is the total length of its arcs. A path with no vertex repetition is called simple.

We study the following problems Exact Path(α), Path Gaps, Short Path Gaps and Long Path Gaps of finding a simple path from a given vertex s to a given vertex t in the graph G. Let integer numbers f i , f i , i = 1, . . . , k, be given such that

L - Σ ≤ f 1 ≤ f 1 < f 2 ≤ f 2 < • • • < f k ≤ f k ≤ L +
Σ , where L - Σ = a∈A,l(a)≤0 l(a) is the total non-positive arc length and L + Σ := a∈A,l(a)>0 l(a) is the total positive arc length. Here we assume that any sum is equal to zero if it is taken over an empty set. Denote [f , f ] = {f , f + 1, . . . , f }.

Problem Exact Path(α): Given number α, find a simple path P from vertex s to vertex t in the graph G such that its length L(P ) = α.

Problem Path Gaps: Find a simple path P from vertex s to vertex t in the graph G such that the length L(P ) ∈ {[f 1 , f 1 ], . . . , [f k , f k ]}. We call intervals [f i , f i ], i = 1, . . . , k, forbidden (path length) gaps. The length of a path should not fall into these gaps.

We also study three special cases of the problem Path Gaps: the case k = 2 of two forbidden gaps [f 1 , f 1 ] and [f 2 , f 2 ], the case k = 1 of a single forbidden gap [f 1 , f 1 ], and a sub-case of the latter case, in which a single path length α is forbidden, that is,

f 1 = f 1 = α.
We denote these cases as Path-2-Gaps, Path-1-Gap and Path No(α), respectively.

Problem Short (Long) Path Gaps: Differs from Path Gaps in that a shortest (longest) simple path with the length not from the forbidden gaps has to be found.

Occasionally, we will assume that graph G is undirected, which will be explicitly indicated.

Problems Path Gaps and Short Path Gaps appear in route planning from one point of a network to another such that the arrival time does not fall into the given time intervals when the service required at the destination point is not available. This situation is similar to that in the vehicle routing problems with time windows, see, for example, Bräysy and Gendreau [START_REF] Bräysy | Vehicle routing problem with time windows, part I: Route construction and local search algorithms[END_REF] for the formulation and a survey of the results for these problems. The problem Long Path Gaps can be used for modeling a situation, in which profits are collected over the route segments while traveling from one point of a network to another. If the total profit is less than a given value B > 0, then it is not worth traveling. The problem is to find a route such that the total profit is maximized and it does not fall into the forbidden gap [0, B]. It is clear that the forbidden gap constraint is redundant if the goal is to find an exact solution. However, the problem is NP-hard in general, and the gap constraint is essential for an approximate solution. Vehicle routing problems with profits have been studied by Archetti et al. [START_REF] Archetti | Chapter 10: Vehicle routing problems with profits[END_REF]. In a situation of goods collection over segments of a path and their transportation in containers, there can be a requirement of container capacity utilization, leading to the forbidden gaps. For example, assume that the capacity of any container is 30 goods, and each container is required to be filled with at least 25 goods. A fixed number of goods associated with a path segment has to be collected if this segment is visited. In this situation, the total number of collected goods should fall into the intervals [START_REF] Leclerc | Polynomial time algorithms for exact matching problems[END_REF][START_REF] Milanic | The exact weighted independent set problem in perfect graphs and related graph classes[END_REF], [50,60], [75,90], [100,120],

[125, ∞], and the forbidden intervals are [0,24], [START_REF] Papadimitriou | The complexity of restricted spanning tree problems[END_REF]49], [61,74], [91,99] and [121,124]. Feasible loads of the containers can be decided after a feasible path has been determined.

To the best of our knowledge, no literature exists on problems with the forbidden objective values gaps. The only exception is our recent paper [START_REF] Dolgui | Knapsack problem with objective value gaps[END_REF] on a 0-1 knapsack problem with the forbidden objective function values. On the other hand, several exact value (or exact cost) combinatorial problems have been studied in the literature, which concern the existence of a solution with a given objective function value. The exact value assignment problem has been studied by Papadimitriou and Yannakakis [START_REF] Papadimitriou | The complexity of restricted spanning tree problems[END_REF] who proved its NP-completeness in the ordinary sense, and Karzanov [START_REF] Karzanov | Maximum matching of given weight in complete and complete bipartite graphs[END_REF] who developed a polynomial time algorithm for the case of 0-1 costs. Pseudo-polynomial time algorithms for the exact value spanning tree problem, the exact value perfect matching problem on planar graph, the exact value cycle sum problem on planar directed graph and the exact value cut problem on planar or toroidal graphs have been presented by Leclerc [START_REF] Leclerc | Polynomial time algorithms for exact matching problems[END_REF] and Barahona and Pulleyblank [START_REF] Barahona | Exact aborescences, matchings and cycles[END_REF]. A number of computational complexity and algorithmic results for the exact weight (maximum) independent set problem on various classes of graphs have been obtained by Milanic and Monnot [START_REF] Milanic | The exact weighted independent set problem in perfect graphs and related graph classes[END_REF]. Computational complexity of the exact weight subgraph problems, in which the number of vertices of the subgraph is a constant, has been studied by Vassilevska and Williams [START_REF] Vassilevska | Finding, minimizing, and counting weighted subgraphs[END_REF] and Abboud and Lewi [START_REF] Abboud | Exact weight subgraphs and the k-sum conjecture[END_REF]. Lopéz et al. [START_REF] Lopéz | Solving the target-value search problem[END_REF] studied the problem Exact Path(α), which they showed to be NP-complete and suggested modifications of the goal search (A * ) and bidirectional search algorithms for the solution. The problem Exact Path(α) can also be formulated as a special case of a constrained path problem, which is to maximize path length, subject to the constraint that the path length does not exceed a certain value, or to minimize the path length, subject to the constraint that the path length is at least a certain value. There exists a bulk of the literature on the constrained and bi-objective path problems, see, for example, Joksch [START_REF] Joksch | The shortest route problem with constraints[END_REF], Dial [12], Hansen [START_REF] Hansen | Bicriterion path problems, in: Theory and applications[END_REF], Aneja et al. [START_REF] Aneja | Shortest chain subject to side constraints[END_REF], Desrochers [START_REF] Desrochers | La fabrication d'horaires de travail pour les conducteurs d'autobus par une methode de generation de colonnes[END_REF], Warburton [START_REF] Warburton | Approximation of Pareto optima in multiple-objective, shortest path problems[END_REF], Hassin [START_REF] Hassin | Approximation schemes for the restricted shortest path problem[END_REF], Lorenz and Raz [START_REF] Lorenz | A simple efficient approximation scheme for the restricted shortest path problem[END_REF], Ergun et al. [START_REF] Ergun | An improved FPTAS for the restricted shortest path problem[END_REF], Righini and Salani [START_REF] Righini | Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints[END_REF], Boland et al. [START_REF] Boland | Accelerated label setting algorithms for the elementary resource constrained shortest path problem[END_REF], Garcia [START_REF] Garcia | Resource constrained shortest paths and extensions[END_REF],

Tsaggouris and Zaroliagis [START_REF] Tsaggouris | Multiobjective optimization: Improved FPTAS for shortest paths and non-linear objectives with applications[END_REF] and Bruegem et al. [START_REF] Breugem | Analysis of FPTASes for the multiobjective shortest path problem[END_REF]. We will present new observations about the relations between the problem Exact Path(α) and other path problems with the forbidden gaps.

The rest of the paper is organized as follows. In the next section, we describe connections of the new problems with the earlier studied problems that provide a fairly complete computational complexity classification of the new problems and some new algorithmic results.

Section 3 studies the case in which the graph is acyclic and the arc lengths are non-negative.

While the problem Exact Path(α) and any of the problems Path Gaps, Short Path Gaps and Long Path Gaps with at least two forbidden gaps are NP-hard for this special case, an efficient approximation scheme is suggested, which delivers a solution with value close to the optimum but, possibly, violating a gap constraint with a given relative error. Polynomial time algorithms are presented for a more restrictive special case of these problems, in which forbidden gaps are polynomially bounded but the arc lengths are not. The paper concludes with a table of the obtained results and suggestions for future research.

Connections with the earlier studied problems

Observe that if graph G contains directed cycles, then the problems Exact Path(α) and Path-1-Gap are NP-complete in the strong sense even if the arc lengths are all equal to one because the NP-complete problem Hamiltonian Path (Garey and Johnson [START_REF] Garey | Computers and intractability: a guide to the theory of NPcompleteness[END_REF]) reduces to Exact Path(α) by setting α = n -1 and it reduces to

Path-1-Gap by setting [f 1 , f 1 ] = [1, n -2].
We further abbreviate directed acyclic (multi)graph to DAG. Assume that G is a DAG.

In this case, Exact Path(α) is NP-complete in the ordinary sense as it was mentioned by Lopéz et al. [START_REF] Lopéz | Solving the target-value search problem[END_REF]. Furthermore, it is pseudo-polynomially solvable by the following folkloric dynamic programming algorithm, denoted as DP-All-Lengths. This algorithm scans vertices in a topological order (cf. Cormen et al. [START_REF] Cormen | Introduction to algorithms[END_REF]) and constructs paths from vertex s to the successor vertices j. A state (j, f ) is associated with a path from vertex s to vertex j, where f is the length of this path. If a complete path P 0 from vertex s to vertex t with length L(P 0 ) goes via a vertex j and a sub-path of P 0 is in the state (j, f ), then any (incomplete) path in this state can be extended to a complete path P from s to t with the same length

L(P ) = L(P 0 ).
Algorithm DP-All-Lengths recursively generates states (j, f ). Let S(j) denote the set of states (j, f ) generated for vertex j, which differ by the path lengths f . The initialization is S(s) = {(s, 0)}. Vertex s is labeled. In the general recursion step, a vertex j is identified whose predecessor vertices i are all labeled. Since G is a DAG, such a vertex always exists.

Set S(j) of states of the identified vertex is calculated as follows.

S(j)

:= j, f + l(a (r) ij ) | a (r) ij ∈ A, (i, f ) ∈ S(i) .
After that, vertex j is labeled and the next vertex with all predecessor vertices labeled is identified. Ultimately, set S(t) is generated, and the corresponding paths from s to t are found by backtracking. If a state (t, α) ∈ S(t), then the problem Exact Path(α) has a solution.

Otherwise, it has no solution. The algorithm DP-All-Lengths can be implemented to run

in O m(|L - Σ | + L + Σ ) time.
Observe that the problem Exact Path(α) is a special case of the problem Path-2-Gaps: Recently, several publications appeared that study the so-called Next-to-Shortest Path problem, which asks for a path from s to t in a graph G of the second shortest length.

an instance of Exact Path(α) is an instance of Path-2-Gaps with gaps [f 1 , f 1 ] = [L - Σ , α-1] and [f 2 , f 2 ] = [α + 1, L + Σ ].
Lalgudi and Papaefthymiou [START_REF] Lalgudi | Computing strictly-second shortest paths[END_REF] proved that this problem is strongly NP-complete if graph G contains directed cycles and arc lengths are non-negative. It also follows from their results that the problem is solvable in O(n+m) time if G is a DAG in this case. Computational complexity is open if the graph contains directed cycles and the arc lengths are strictly positive. The latter case is solvable in O(n 3 ) time for planar graphs, as shown by Wu and Wang [START_REF] Wu | The next-to-shortest path problem on directed graphs with positive edge weights[END_REF]. If the graph is undirected, then the problem is polynomially solvable. For strictly positive edge lengths, algorithms with running times O(n 3 m), O(n 3 ) and O(n 2 ) were successively presented by Krasikov and Noble [START_REF] Krasikov | Finding next-to-shortest paths in a graph[END_REF], Li et al. [START_REF] Li | Improved algorithm for finding next-to-shortest paths[END_REF] and Kao et al. [START_REF] Kao | A quadratic algorithm for finding next-to-shortest paths in graphs[END_REF]. For non-negative edge lengths, an O(n 6 m) time algorithm is presented by Zhang and Nagamochi [START_REF] Zhang | The next-to-shortest path in undirected graphs with nonnegative weights[END_REF]. Below we will assume that the path in the Next-to-Shortest Path problem is required to be simple. • if graph G is directed and planar and arc lengths are strictly positive, then Path No(α) can be solved in O(n 3 ) time [START_REF] Wu | The next-to-shortest path problem on directed graphs with positive edge weights[END_REF];

• if graph G is undirected and arc lengths are strictly positive, then Path No(α) can be solved in O(n 2 ) time [START_REF] Kao | A quadratic algorithm for finding next-to-shortest paths in graphs[END_REF];

• if graph G is undirected and arc lengths are non-negative, then Path No(α) can be solved in O(n 6 m) time [START_REF] Zhang | The next-to-shortest path in undirected graphs with nonnegative weights[END_REF].

Let us now show that for graphs with directed cycles and non-negative arc lengths the problem Path No(α) is difficult. Proof. Fortune et al. [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] proved that the problem Two Disjoint Paths is NP-complete in the strong sense. In this problem, given vertices s 1 , t 1 , s 2 and t 2 of a directed graph with directed cycles, the question concerns the existence of a simple path from s 1 to t 1 and a simple

DAGs with non-negative arc lengths

In this section, we assume that G is a DAG and the arc lengths are non-negative integer numbers. The latter assumption implies L - Σ = 0. For this special case, the problem Exact Path(α) and any of the problems Path Gaps, Short Path Gaps and Long Path Gaps with at least two forbidden gaps are NP-hard, as it is indicated in Section 2. In the following sub-section, an approximation scheme is described for this special case, which delivers a solution with value close to the optimum with a given relative error ε, but, perhaps, inside a forbidden gap. In Sub-section 3.2, we suggest polynomial time algorithms for a more restrictive special case of these problems, in which forbidden gaps values are polynomially bounded but the arc lengths are not.

Approximation

Let ε be an arbitrary given number such that 0 < ε ≤ 1. We first suggest a family of algorithms (approximation scheme), each of which is specified by ε and a positive integer number β, and is denoted as DP ε,β , such that, for any instance of the problem Exact Path(α) with α ∈ {0, 1, . . . , β}, which has a solution, algorithm DP ε,β finds in O( m ε ) time a (simple) path from s to t in DAG G with non-negative integral arc lengths, whose length

F (ε,α,β) satisfies relations F (ε,α,β) ≤ β and |α -F (ε,α,β) | ≤ εβ.
Algorithm DP ε,β is a modification of the algorithm DP-All-Lengths. The modification concerns generation of the sets of states S(j). After the set

S(j) = j, f + l(a (r) ij ) | a (r) ij ∈ A, (i, f ) ∈ S(i)
has been produced, states (j, f ) with path lengths f ≥ β + 1 are excluded from it and set S (1) (j) = {(j, f ) | (j, f ) ∈ S(j), f ≤ β} is generated. Further, the set S (1) (j) is partitioned into disjoint subsets X (1) (j), X (2) (j), . . . , X (u) (j) such that |f 1 -f 2 | ≤ εβ for any states (f 1 , j) and (f 2 , j) from the same subset. This partitioning can be done in O(|S (1) (j)|) time by calculating value f /(εβ) for each (f, j) ∈ S (1) (j) and assigning states with the same value f /(εβ) to the same subset X (h) (j) such that h = f /(εβ) . The number of the subsets does not exceed O(1/ε). Since empty subsets are of no interest, they are removed and the non-empty subsets are re-numbered X (1) (j), X (2) (j), . . . , X (u) (j).

In each non-empty subset X (h) (j), minimum and maximum numbers, f (h,j) min and f (h,j) max , which are the same number if |X (h) (j)| = 1, are selected, h = 1, . . . , u. Thus, for any state (j, f ) ∈ S (1) (j), there is an index h ∈ {1, . . . , u} such that f

(h,j) min ≤ f ≤ f (h,j) max and f (h,j) max -f (h,j) min ≤ εβ. Finally, set S (2) (j) = {(j, f (h,j) min ), (j, f (h,j) max ) | h = 1, .
. . , u} is generated, original set S(j) is updated such that S(j) := S (2) (j), vertex j is labeled, and the next vertex with all predecessor vertices labeled is identified. We have |S (2)

(j)| ≤ 2u = O(1/ε). Therefore, |S (1) (j)| ≤ i∈K j |S (2) i | = O(|K j |/ε)
, where K j is the set of vertices immediately preceding j in G, and |K j | is the indegree of j, for any j ∈ V .

Recall that the running time of the optimal algorithm

DP-All-Lengths is O m(|L - Σ | + L + Σ ) , where m = j∈V |K j | and O(|L - Σ | + L + Σ
) is an upper bound on the number of distinct path lengths. Similarly, the running time of the approximation algorithm DP ε,β can be evaluated as O( j∈V |K j |U ), where U is an upper bound on the number of distinct "rounded" path lengths associated with the same vertex. We have U ≤ O(1/ε), therefore, DP ε,β can be implemented to run in O( m ε ) time. We next prove an important property of the algorithm DP ε,β .

Theorem 1 If problem Exact Path(α), α ≤ β, has solution, then there exists a state (t, F (ε,α,β) ) ∈ S(t) in the algorithm DP ε,β and the corresponding path with length

F (ε,α,β) such that F (ε,α,β) ≤ β and |α -F (ε,α,β) | ≤ εβ.
Proof. Let path (j 1 , . . . , j r ) be a solution of Exact Path(α), where j 1 = s and j r = t.

The proof can be given by an induction on j i . Assume that, for a state (j i , f ) in DP-All-Lengths, 1 ≤ i ≤ r -1, preceding the final state (t, α), there exists a state (j i , f 1 )

in the algorithm DP ε,β such that f 1 ≤ f ≤ β and |f 1 -f | ≤ εβ.
This assumption is satisfied for j i = s. Then there exist states (j i , f

(h,j i ) min ) and (j i , f (h,j i ) max ) in DP ε,β such that f (h,j i ) min ≤ f 1 ≤ f (h,j i ) max ≤ β and f (h,j i ) max -f (h,j i ) min
≤ εβ. These two relations, together with

f 1 ≤ f ≤ β and |f 1 -f | ≤ εβ, imply that for either f 2 = f (h,j i ) min or f 2 = f (h,j i ) max we have f 2 ≤ f ≤ β and |f 2 -f | ≤ εβ. The state (j i , f 2 ) is generated in DP ε,β . Further, if state (j i , f )
is extended to a state (j i+1 , f + l), preceding the final state (t, α), in DP-All-Lengths,

then the state (j i , f 2 ) is extended to the state (j i+1 , f 2 + l) in DP ε,β such that f 2 + l ≤ f + l and |(f 2 + l) -(f + l)| ≤ εβ.
Repetition of this inductive argument for all vertices j 1 , . . . , j r completes the proof.

We now describe our ultimate approximation scheme {E ε }. For any given ε,

0 < ε ≤ 1, algorithm E ε consists of applications of the algorithm DP ε/2,β for β ∈ W := {0, (1 + ε/2) , (1 + ε/2) 2 , . . . , (1 + ε/2) w , L + Σ }, where w is defined to satisfy (1 + ε/2) w < L + Σ and (1 + ε/2) w+1 ≥ L + Σ .
By taking logarithm with base two from both sides of the latter relation and assuming that w is a real number, we obtain that this relation is satisfied for

w = (log 2 L + Σ )/ log 2 (1 + ε/2) -1. Since log 2 (1 + ε/2) ≥ ε/2 for 0 < ε ≤ 2, we know that w ≤ 2(log 2 L + Σ )/ε -1. Thus, |W | ≤ 2(log 2 L + Σ )/ε, and algorithm E ε runs in O( m ε 2 log 2 L + Σ )
time.

The following theorem establishes properties of solutions delivered by the algorithm E ε .

Theorem 2 For any instance of any of the problems Path Gaps, Short Path Gaps and

Long Path Gaps on a DAG with non-negative arc lengths that has a solution, algorithm E ε finds a solution (path from s to t), whose length F (ε) satisfies |F (ε) -F | ≤ εF , where F ∈ {F 0 , F * }, F 0 is the value of any feasible solution of the problem Path Gaps and F * is the optimal value in the problems Short Path Gaps and Long Path Gaps.

Proof. Observe that, for any value α, 0 ≤ α ≤ L + Σ , there exists a value β ∈ W such that α ≤ β ≤ α(1 + ε/2). By Theorem 1, for these α and β algorithm DP ε/2,β will find a solution with value F (ε/2,α,β) for the problem Exact Path(α), which satisfies |F (ε/2,α,β) -α| ≤ εβ/2.

Taking into account β ≤ α(1+ε/2) and 0 < ε ≤ 1, we obtain |F (ε/2,α,β) -α| ≤ ε(1+ε/2)α/2 ≤ εα. By substituting α with F , we see that the statement of the theorem is satisfied by setting

F (ε) = F (ε/2,F,β 0 )
, where β 0 is the number from the set W such that

F ≤ β 0 ≤ F (1 + ε/2).
It follows from Theorem 2 and the definition of the absolute value that if there exists a feasible solution of the problem Path Gaps or an optimal solution of any of the problems Short Path Gaps and Long Path Gaps with value F , F ∈ {F 0 , F * }, such that

f i + 1 ≤ F ≤ f i+1 -1, i ∈ {1, . . . , k}, then (1 -ε)(f i + 1) ≤ (1 -ε)F ≤ F (ε) ≤ F (1 + ε) ≤ (1 + ε)(f i+1 -1),
which means that ε is a guaranteed relative error of the gap constraint violation. This type of approximation with respect to the bounding constraints has been used, for example, by Brucker et al. [START_REF] Brucker | Batch scheduling with deadlines on parallel machines[END_REF] and Cheng et al. [START_REF] Cheng | Bicriterion single machine scheduling with resource dependent processing times[END_REF] for NP-hard scheduling problems.

By a similar argument, if the optimal value F * of any of the problems Short Path

Gaps and Long Path Gaps is at least εF * units away from any forbidden value, then the algorithm E ε is guaranteed to find a feasible solution, in which case {E ε } is a Fully Polynomial Time Approximation Scheme (FPTAS), see, for example, FPTASs of Hansen [START_REF] Hansen | Bicriterion path problems, in: Theory and applications[END_REF],

Hassin [START_REF] Hassin | Approximation schemes for the restricted shortest path problem[END_REF], Lorenz and Raz [START_REF] Lorenz | A simple efficient approximation scheme for the restricted shortest path problem[END_REF] and Tsaggouris and Zaroliagis [START_REF] Tsaggouris | Multiobjective optimization: Improved FPTAS for shortest paths and non-linear objectives with applications[END_REF] for the constrained and multi-objective shortest path problems. The two-stage approach (algorithm DP ε,β first and then its application for β ∈ W ) makes the approximation scheme {E ε } different from the existing FPTASs.

Note that recognizing the fact that the optimal value F * is at least εF * units away from any forbidden value for the problem Short Path Gaps with two forbidden intervals [0, α -εα] and [α + εα, L + Σ ] is as difficult as the problem Exact Path(α), which is NP-complete, see Section 2.

The results of this sub-section are summarized in the following theorem. ), which finds a solution, possibly infeasible, with any given relative error ε with respect to the optimal objective value and the gap constraints.

The type of approximation in this sub-section is related to the concept of resource augmentation, which is used in the analysis of approximation algorithms, see Lucarelli et al. [START_REF] Lucarelli | Online nonpreemptive scheduling in a resource augmentation model based on duality[END_REF].

According to this concept, an approximation algorithm is allowed to find a solution in the domain which is broader than the feasible domain of the original problem. L - Σ = 0 and L + Σ ≤ mP I in this case. In this sub-section, we study the case in which f k ≤ P I . We stress that the arc lengths are not assumed to be polynomially bounded. This case cannot be solved by a direct application of the algorithm DP-All-Lengths. Let us call an arc short if its length does not exceed P I . Otherwise, an arc is called long. Recall that the considered graph is a DAG and the arc lengths are non-negative.

Polynomially bounded forbidden path lengths

First of all, we apply the Breadth-First-Search algorithm (cf. Cormen et al. In this case, an optimal solution of the classic longest path problem is an optimal solution for the problem Long Path Gaps. Indeed, either the former solution includes a long arc, and therefore, it is feasible with respect to the gaps, or its length is at least the length of a long arc, and again, it is feasible with respect to the gaps. Recall that a long arc is present in the new graph and consider now any of the problems Path Gaps and Short Path Gaps. There are two sub-cases to consider with respect to a feasible (respectively, optimal) solution of this problem: 1) this solution includes no long arc, and 2) it includes at least one long arc. For the sub-case 1), remove long arcs from the graph and apply algorithm DP-All-Lengths to find a feasible (for Path Gaps) or optimal (for Short Path Gaps) solution in O(m 2 P I ) time. For the case 2), solve at most m classic shortest path problems, each of which is specified by a long arc a. The length of this arc is re-set to be a sufficiently small number, for example, l(a) := -L + Σ . In this case, any shortest path will necessarily go via the arc a. Denote such a path as P a . Since arc a is originally long, path P a is feasible with respect to the gaps. Feasible solution for the problem Path Gaps or optimal solution for the problem Short Path Gaps is the best solution with respect to the original arc lengths among at most m + 1 solutions: one solution for the sub-case 1) and at most m solutions for the sub-case 2). It can be found in O(m 2 P I + mn) time.

Thus, the case with non-negative arc lengths and f k ≤ P I is as easy as the case with polynomially bounded absolute values of the arc lengths, and the following theorem holds.

Conclusions and suggestions for future research

The main results of this paper are summarized in Table 1. There, "NP-h" and "sNP-h" abbreviate "NP-hard" and "strongly NP-hard", and "SPP" and "LPP" abbreviate "shortest path problem" and "longest path problem".

In the future, it is interesting to study path problems with exact and forbidden lengths for various specific graph classes.

  Therefore, Path-2-Gaps is NP-complete in the strong sense for graphs with directed cycles and unit arc lengths and it is NP-complete in the ordinary sense for DAGs with non-negative arc lengths. Furthermore, any instance of Path-2-Gaps can be solved by solving the same instance of Exact Path(α) for all α which are not from the gaps. Therefore, Path-2-Gaps is pseudo-polynomially solvable for DAGs, and it is polynomially solvable for DAGs with polynomially bounded absolute values of arc lengths. Since the problem Path-2-Gaps is a special case of any of the problems Path Gaps, Short Path Gaps and Long Path Gaps, the latter problems are NP-hard in the strong sense for graphs with directed cycles and unit arc lengths and they are NP-hard in the ordinary sense for DAGs with non-negative arc lengths. Let there be an algorithm with time complexity O(T ) for the problem Exact Path(α). By running this algorithm for α = L - Σ , L - Σ + 1, . . . , L + Σ , any of the problems Path Gaps, Short Path Gaps and Long Path Gaps can be solved in O T (|L - Σ | + L + Σ ) time. If G is a DAG, then, by scanning path lengths in the set S(t) generated by the algorithm DP-All-Lengths, and selecting appropriate lengths and corresponding paths, all the problems Path Gaps, Short Path Gaps and Long Path Gaps can be solved in O m(|L - Σ | + L + Σ ) time. Below more results are established for the problems Path-1-Gap and Path No(α). Observation 1 Problem Path-1-Gap reduces to solving both classic shortest and longest path problems. Proof. Note that an instance of the problem Path-1-Gap and the corresponding instance of any of the two above mentioned classic path problems have a solution only if a path from s to t exists. Assume that it is the case. Let L short and L long denote lengths of the shortest and longest simple paths, respectively, in the classic problems. If [L short , L long ] ⊆ [f 1 , f 1 ], then the instance of the problem Path-1-Gap has no solution. Otherwise, if L short < f 1 , then the shortest simple path is a solution of the instance of the problem Path-1-Gap, and if L long > f 1 , then the longest simple path is a solution of this instance. Since both classic shortest path and longest path problems can be solved in O(n + m) time for DAGs (cf. Cormen et al. [10]), the following corollary follows. Corollary 1 If G is a DAG, then the problem Path-1-Gap, and hence, the problem Path No(α), can be solved in O(n + m) time.

Observation 2 Corollary 2

 22 Problem Path No(α) reduces to solving both the classic shortest path problem and the Next-to-Shortest Path problem. Proof. Similar to the proof of Observation 1, assume without loss of generality that a path from s to t exists. Let L short and L short + δ, δ > 0, denote lengths of the shortest and next-toshortest simple paths, respectively. If L short = α, then the shortest simple path is a solution of the instance of the problem Path No(α). If L short = α, then the next-to-shortest simple path is a solution of this instance. The following special cases of the problem Path No(α) are polynomially solvable:

Observation 3

 3 If graph G contains directed cycles and the arc lengths are all equal to 0 but one arc length is equal to 1, then any of the problems Exact Path(α), Path No(α), Path-1-Gap, Path-2-Gaps, Path Gaps, Short Path Gaps and Long Path Gaps is NP-complete in the strong sense.

path from s 2

 2 to t 2 such that these two paths have no common vertex. It can easily be verified that an instance of Two Disjoint Paths has a solution if and only if Exact Path(α) for α = 1 (respectively, Path No(α) for α = 0) has a solution for the same graph as in Two Disjoint Paths but with an extra arc (t 1 , s 2 ) whose length is equal to one and with all other arc lengths equal to zero. Therefore, Exact Path(α) for α = 1 and Path No(α) for α = 0 are NP-complete in the strong sense. The other problems mentioned in the observation are generalizations of either the problem Path No(α) or the problem Exact Path(α) (for Path-2-Gaps), and therefore, they cannot be easier.It is worth noting that the problem Two Disjoint Paths in an undirected graph is solvable in almost linear time by the algorithm of Tholey[START_REF] Tholey | Solving the 2-disjoint paths problem in nearly linear time[END_REF].

Theorem 3

 3 If G is a DAG and arc lengths are non-negative, then problems Path Gaps, Short Path Gaps and Long Path Gaps possess an approximation scheme {E ε } with running time O( m ε 2 log 2 L + Σ

Let

  I denote the input length of any of the problems Path Gaps, Short Path Gaps and Long Path Gaps in binary encoding, I = O a∈A log 2 |l(a)| + k i=1 (log 2 |f i | + log 2 |f i |) , and let P I denote a polynomial of I. If the absolute values |l(a)| of the arc lengths are bounded by the polynomial P I , then the problems Path Gaps, Short Path Gaps and Long Path Gaps are solvable by the algorithm DP-All-Lengths in O(m 2 P I ) time for DAGs, because

  [START_REF] Cormen | Introduction to algorithms[END_REF]) to modify the original graph in O(n + m) time so that every arc belongs to at least one path from s to t. If the new graph contains no long arcs, then the problems Path Gaps, Short Path Gaps and Long Path Gaps can be solved by the algorithm DP-All-Lengths in O(m 2 P I ) time, because L - Σ = 0 and L + Σ ≤ mP I . Assume that the new graph contains at least one long arc.

Theorem 4

 4 If G is a DAG, arc lengths are non-negative and forbidden path lengths are polynomially bounded such that f k ≤ P I , then the problem Long Path Gaps is solvable in O(m 2 P I ) time and any of the problems Path Gaps and Short Path Gaps are solvable in O(m 2 P I + mn) time.