Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

Fast Polynomial-Space Algorithms Using Inclusion-Exclusion

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in $\mathcal{O}^{\star}(2^{k}c)$ time and $\mathcal{O}^{\star}(c)$ space, where the $\mathcal{O}^{\star}$ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give $\mathcal{O}^{\star}(2^{n})$ -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.     

On the Exact Complexity of Evaluating Quantified k -CNF

We relate the exponential complexities 2 ^s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 ^cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma.     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

Integrated damping parameter and control design in structural systems for \bf{\mathcal{H}^2} and {\mathcal{H}^{\infty}} specifications

The paper presents a linear matrix inequality (LMI)-based approach for the simultaneous optimal design of output feedback control gains and damping parameters in structural systems with collocated actuators and sensors. The proposed integrated design is based on simplified $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ norm upper bound calculations for collocated structural systems. Using these upper bound results, the combined design of the damping parameters of the structural system and the output feedback controller to satisfy closed-loop $\mathcal{H}^2$ or $\mathcal{H}^{\infty}$ performance specifications is formulated as an LMI optimization problem with respect to the unknown damping coefficients and feedback gains. Numerical examples motivated from structural and aerospace engineering applications demonstrate the advantages and computational efficiency of the proposed technique for integrated structural and control design. The effectiveness of the proposed integrated design becomes apparent, especially in very large scale structural systems where the use of classical methods for solving Lyapunov and Riccati equations associated with $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ designs are time-consuming or intractable.     

Hyper-Hamiltonian laceability of balanced hypercubes

The balanced hypercube, proposed by Wu and Huang, is a new variation of hypercube. The particular property of the balanced hypercube is that each processor has a backup processor that shares the same neighborhood. A Hamiltonian bipartite graph with bipartition $V_{0}\cup V_{1}$ is said to be Hamiltonian laceable if there is a Hamiltonian path between any two vertices $x\in V_{0}$ and $y\in V_{1}$ . A graph $G$ is hyper-Hamiltonian laceable if it is Hamiltonian laceable and, for any vertex $v\in V_{i}$ , $i\in \{0,1\}$ , there is a Hamiltonian path in G–v between any pair of vertices in $V_{1-i}$ . In this paper, we mainly prove that the balanced hypercube is hyper-Hamiltonian laceable.     

Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification

This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time, where m is the number of edges in the given graph G, n is the number of nodes, and D is G’s diameter. On the other hand, we show that any MST verification algorithm must send $\tilde{\varOmega}(m)$ messages and incur $\tilde{\varOmega}(\sqrt{n} + D)$ time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of $\tilde{\varOmega}(m)$ messages and $\tilde{\varOmega}(\sqrt{n} + D)$ time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time. Specifically, the best known time-optimal algorithm (using ${\tilde{O}}(\sqrt {n} + D)$ time) requires O(m+n ^3/2) messages, and the best known message-optimal algorithm (using ${\tilde{O}}(m)$ messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.     

Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.     

On matrices, automata, and double counting in constraint programming

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.     

Efficient controller synthesis for a fragment of \hbox {MTL}_{0, \infty }

In this paper we offer an efficient controller synthesis algorithm for assume-guarantee specifications of the form $\varphi _1 \wedge \varphi _2 \wedge \cdots \wedge \varphi _n \rightarrow \psi _1 \wedge \psi _2 \wedge \cdots \wedge \psi _m$ . Here, $\{\varphi _i,\psi _j\}$ are all safety-MTL $_{0, \infty }$ properties, where the sub-formulas $\{\varphi _i\}$ are supposed to specify assumptions of the environment and the sub-formulas $\{\psi _j\}$ are specifying requirements to be guaranteed by the controller. Our synthesis method exploits the engine of Uppaal-Tiga and the novel translation of safety- and co-safety-MTL $_{0, \infty }$ properties into under-approximating, deterministic timed automata. Our approach avoids determinization of Büchi automata, which is the main obstacle for the practical applicability of controller synthesis for linear-time specifications. The experiments demonstrate that the chosen specification formalism is expressive enough to specify complex behaviors. The proposed approach is sound but not complete. However, it successfully produced solutions for all the experiments. Additionally we compared our tool with Acacia+ and Unbeast, state-of-the-art LTL synthesis tools; and our tool demonstrated better timing results, when we applied both tools to the analogous specifications.     

Quantum discord in spin systems with dipole–dipole interaction

The behavior of total quantum correlations (discord) in dimers consisting of dipolar-coupled spins 1/2 are studied. We found that the discord $Q=0$ at absolute zero temperature. As the temperature $T$ increases, the quantum correlations in the system increase at first from zero to its maximum and then decrease to zero according to the asymptotic law $T^{-2}$ . It is also shown that in absence of external magnetic field $B$ , the classical correlations $C$ at $T\rightarrow 0$ are, vice versa, maximal. Our calculations predict that in crystalline gypsum $\hbox {CaSO}_{4}\cdot \hbox {2H}_{2}{\hbox {O}}$ the value of natural $(B=0)$ quantum discord between nuclear spins of hydrogen atoms is maximal at the temperature of 0.644  $\upmu $ K, and for 1,2-dichloroethane $\hbox {H}_{2}$ ClC– $\hbox {CH}_{2}{\hbox {Cl}}$ the discord achieves the largest value at $T=0.517~\upmu $ K. In both cases, the discord equals $Q\approx 0.083$  bit/dimer what is $8.3\,\%$ of its upper limit in two-qubit systems. We estimate also that for gypsum at room temperature $Q\sim 10^{-18}$  bit/dimer, and for 1,2-dichloroethane at $T=90$  K the discord is $Q\sim 10^{-17}$  bit per a dimer.     

Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks

Although the earliest-deadline-first (EDF) policy is known to be optimal for preemptive real-time task scheduling in uniprocessor systems, the schedulability analysis problem has recently been shown to be $\mathit{co}\mathcal{NP}$ -hard. Therefore, approximation algorithms, and in particular, approximations based on resource augmentation have attracted a lot of attention for both uniprocessor and multiprocessor systems. Resource augmentation based approximations assume a certain speedup of the processor(s). Using the notion of approximate demand bound function (dbf), in this paper we show that for uniprocessor systems the resource augmentation factor is at most $\frac{2e-1}{e} \approx1.6322$ , where e is the Euler number. We approximate the dbf using a linear approximation when the analysis interval length of interest is larger than the relative deadline of the task. For identical multiprocessor systems with M processors and constrained-deadline task sets, we show that the deadline-monotonic partitioning (that has been proposed by Baruah and Fisher) with the approximate dbf leads to an approximation factor of $\frac{3e-1}{e}-\frac{1}{M} \approx 2.6322-\frac{1}{M}$ with respect to resource augmentation. We also show that the corresponding factor is $3-\frac{1}{M}$ for arbitrary-deadline task sets. The best known results so far were $3-\frac{1}{M}$ for constrained-deadline tasks and $4-\frac {2}{M}$ for arbitrary-deadline ones. Our tighter analysis exploits the structure of the approximate dbf directly and uses the processor utilization violations (which were ignored in all previous analysis) for analyzing resource augmentation factors. We also provide concrete input instances to show that the lower bound on the resource augmentation factor for uniprocessor systems—using the above approximate dbf—is 1.5, and the corresponding bound is 2.5 for identical multiprocessor systems with an arbitrary order of fitting and a large number of processors. Further, we also provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions under the assumption that the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant, which is a more relaxed assumption compared to the assumptions required for deriving such a PTAS in the past.     

Delayed theory combination vs. Nelson-Oppen for satisfiability modulo theories: a comparative analysis

Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ .     

Self-Referential Justifications in Epistemic Logic

This paper is devoted to the study of self-referential proofs and/or justifications, i.e., valid proofs that prove statements about these same proofs. The goal is to investigate whether such self-referential justifications are present in the reasoning described by standard modal epistemic logics such as  $\mathsf{S4}$ . We argue that the modal language by itself is too coarse to capture this concept of self-referentiality and that the language of justification logic can serve as an adequate refinement. We consider well-known modal logics of knowledge/belief and show, using explicit justifications, that $\mathsf{S4}$ , $\mathsf{D4}$ , $\mathsf{K4}$ , and  $\mathsf{T}$ with their respective justification counterparts  $\mathsf{LP}$ , $\mathsf{JD4}$ , $\mathsf{J4}$ , and  $\mathsf{JT}$ describe knowledge that is self-referential in some strong sense. We also demonstrate that self-referentiality can be avoided for  $\mathsf{K}$ and  $\mathsf{D}$ . In order to prove the former result, we develop a machinery of minimal evidence functions used to effectively build models for justification logics. We observe that the calculus used to construct the minimal functions axiomatizes the reflected fragments of justification logics. We also discuss difficulties that result from an introduction of negative introspection.     

Characterization of quantum circulant networks having perfect state transfer

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph G, which is characterized by its circulant adjacency matrix A. Formally, we say that there exists a perfect state transfer (PST) between vertices ${a,b\in V(G)}$ if |F(τ) _ab | = 1, for some positive real number τ, where F(t) = exp(i At). Saxena et al. (Int J Quantum Inf 5:417–430, 2007) proved that |F(τ) _aa | = 1 for some ${a\in V(G)}$ and ${\tau\in \mathbb {R}^+}$ if and only if all eigenvalues of G are integer (that is, the graph is integral). The integral circulant graph ICG _n (D) has the vertex set Z _n = {0, 1, 2, . . . , n ? 1} and vertices a and b are adjacent if ${\gcd(a-b,n)\in D}$ , where ${D \subseteq \{d : d \mid n, \ 1 \leq d < n\}}$ . These graphs are highly symmetric and have important applications in chemical graph theory. We show that ICG _n (D) has PST if and only if ${n\in 4\mathbb {N}}$ and ${D=\widetilde{D_3} \cup D_2\cup 2D_2\cup 4D_2\cup \{n/2^a\}}$ , where ${\widetilde{D_3}=\{d\in D\ |\ n/d\in 8\mathbb {N}\}, D_2= \{d\in D\ |\ n/d\in 8\mathbb {N}+4\}{\setminus}\{n/4\}}$ and ${a\in\{1,2\}}$ . We have thus answered the question of complete characterization of perfect state transfer in integral circulant graphs raised in Angeles-Canul et al. (Quantum Inf Comput 10(3&4):0325–0342, 2010). Furthermore, we also calculate perfect quantum communication distance (distance between vertices where PST occurs) and describe the spectra of integral circulant graphs having PST. We conclude by giving a closed form expression calculating the number of integral circulant graphs of a given order having PST.     

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in ${\mathcal {O}}^{*}(\alpha^{n})$ time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses ${\mathcal {O}}^{*}(1.657^{n})$ time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses ${\mathcal {O}}^{*}(1.6818^{n})$ time and exponential space, and one algorithm that uses ${\mathcal {O}}^{*}(1.8878^{n})$ time and polynomial space.     

Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.