Search

An oriented multigraph is a directed multigraph without directed 2-cycles. Let ${\rm fas}(D)$ denote the minimum size of a feedback arc set in an oriented multigraph $D$. The degree of a vertex is the sum of its out- and in-degrees. In several papers, upper bounds for ${\rm fas}(D)$ were obtained for oriented multigraphs $D$ with maximum degree upper-bounded by a constant. Hanauer (2017) conjectured that ${\rm fas}(D)\le 2.5n/3$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5. We prove a strengthening of the conjecture: ${\rm fas}(D)\le m/3$ holds for every oriented multigraph $D$ with $m$ arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor (1990,1997). It would be interesting to determine $c$ such that ${\rm fas}(D)\le cn$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5 such that the bound is tight. We show that $\frac{5}{7}\le c \le \frac{24}{29} < \frac{2.5}{3}$.

A run of the deferred acceptance (DA) algorithm may contain proposals that are sure to be rejected. We introduce the accelerated deferred acceptance algorithm that proceeds in a similar manner to DA but with sure-to-be rejected proposals ruled out. Accelerated deferred acceptance outputs the same stable matching as DA but does so more efficiently: it terminates in weakly fewer rounds, requires weakly fewer proposals, and final pairs match no later. Computational experiments show that these efficiency savings can be strict.

An oriented graph $D$ is converse invariant if, for any tournament $T$, the number of copies of $D$ in $T$ is equal to that of its converse $-D$. El Sahili and Ghazo Hanna [J. Graph Theory 102 (2023), 684-701] showed that any oriented graph $D$ with maximum degree at most 2 is converse invariant. They proposed a question: Can we characterize all converse invariant oriented graphs? In this paper, we introduce a digraph polynomial and employ it to give a necessary condition for an oriented graph to be converse invariant. This polynomial serves as a cornerstone in proving all the results presented in this paper. In particular, we characterize all orientations of trees with diameter at most 3 that are converse invariant. We also show that all orientations of regular graphs are not converse invariant if $D$ and $-D$ have different degree sequences. In addition, in contrast to the findings of El Sahili and Ghazo Hanna, we prove that every connected graph $G$ with maximum degree at least $3$, admits an orientation $D$ of $G$ such that $D$ is not converse invariant. We pose one conjecture.

Let $G=(V, E)$ be a graph and let each vertex of $G$ has a lamp and a button. Each button can be of $\sigma^+$-type or $\sigma$-type. Assume that initially some lamps are on and others are off. The button on vertex $x$ is of $\sigma^+$-type ($\sigma$-type, respectively) if pressing the button changes the lamp states on $x$ and on its neighbors in $G$ (the lamp states on the neighbors of $x$ only, respectively). Assume that there is a set $X\subseteq V$ such that pressing buttons on vertices of $X$ lights all lamps on vertices of $G$. In particular, it is known to hold when initially all lamps are off and all buttons are of $\sigma^+$-type. Finding such a set $X$ of the smallest size is NP-hard even if initially all lamps are off and all buttons are of $\sigma^+$-type. Using a linear algebraic approach we design a polynomial-time approximation algorithm for the problem such that for the set $X$ constructed by the algorithm, we have $|X|\le \min\{r,(|V|+{\rm opt})/2\},$ where $r$ is the rank of a (modified) adjacent matrix of $G$ and ${\rm opt}$ is the size of an optimal solution to the problem. To the best of our knowledge, this is the first polynomial-time approximation algorithm for the problem with a nontrivial approximation guarantee.

An oriented graph is called $k$-anti-traceable if the subdigraph induced by every subset with $k$ vertices has a hamiltonian anti-directed path. In this paper, we consider an anti-traceability conjecture. In particular, we confirm this conjecture holds when $k\leq 4$. We also show that every sufficiently large $k$-anti-traceable oriented graph admits an anti-path that contains $n-o(n)$ vertices., Comment: 15 pages, 1 figure

Role mining is a technique used to derive a role-based authorization policy from an existing policy. Given a set of users $U$, a set of permissions $P$ and a user-permission authorization relation $\mahtit{UPA}\subseteq U\times P$, a role mining algorithm seeks to compute a set of roles $R$, a user-role authorization relation $\mathit{UA}\subseteq U\times R$ and a permission-role authorization relation $\mathit{PA}\subseteq R\times P$, such that the composition of $\mathit{UA}$ and $\mathit{PA}$ is close (in some appropriate sense) to $\mathit{UPA}$. In this paper, we first introduce the Generalized Noise Role Mining problem (GNRM) -- a generalization of the MinNoise Role Mining problem -- which we believe has considerable practical relevance. Extending work of Fomin et al., we show that GNRM is fixed parameter tractable, with parameter $r + k$, where $r$ is the number of roles in the solution and $k$ is the number of discrepancies between $\mathit{UPA}$ and the relation defined by the composition of $\mathit{UA}$ and $\mathit{PA}$. We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both $r$ and $k$ subject to upper bounds $r\le \bar{r}$ and $k\le \bar{k}$, where $\bar{r}$ and $\bar{k}$ are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter $\bar{r}+\bar{k}$. We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a) we obtained strong support that Gurobi's performance is fixed-parameter tractable, (b) our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies.

A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this paper, we give lower bounds for the maximum weight of bisections of edge-weighted graphs with bounded maximum degree. Our results improve a bound of Lee, Loh, and Sudakov (J. Comb. Th. Ser. B 103 (2013)) for (unweighted) maximum bisections in graphs whose maximum degree is either even or equals 3, and for almost all graphs. We show that a tight lower bound for maximum size of bisections in 3-regular graphs obtained by Bollob\'as and Scott (J. Graph Th. 46 (2004)) can be extended to weighted subcubic graphs. We also consider edge-weighted triangle-free subcubic graphs and show that a much better lower bound (than for edge-weighted subcubic graphs) holds for such graphs especially if we exclude $K_{1,3}$. We pose three conjectures.

Given a natural number $k\ge 2$, we consider the $k$-submodular cover problem ($k$-SC). The objective is to find a minimum cost subset of a ground set $\mathcal{X}$ subject to the value of a $k$-submodular utility function being at least a certain predetermined value $\tau$. For this problem, we design a bicriteria algorithm with a cost at most $O(1/\epsilon)$ times the optimal value, while the utility is at least $(1-\epsilon)\tau/r$, where $r$ depends on the monotonicity of $g$.

In 1981, Bermond and Thomassen conjectured that for any positive integer $k$, every digraph with minimum out-degree at least $2k-1$ admits $k$ vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triangle-free multipartite tournaments and 3-partite tournaments. Furthermore, we characterize 3-partite tournaments with minimum out-degree at least $2k-1$ ($k\geq 2$) such that in each set of $k$ vertex-disjoint directed cycles, every cycle has the same length., Comment: 9 pages, 0 figure

In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kinds of binary action coordination problems in social networks: pure coordination games and anti-coordination games. For both environments, we determine the computational complexity of finding a strategy profile that (i) maximises welfare, (ii) maximises welfare subject to being an equilibrium, and (iii) maximises potential. We show that the complexity of these objectives can vary with the type of coordination problem. Objectives (i) and (iii) are tractable problems in pure coordination games, but for anti-coordination games are NP-hard. Objective (ii), finding the best Nash equilibrium, is NP-hard for both. Our results support the idea that environments in which actions are strategic complements (e.g., technology adoption) facilitate successful coordination more readily than those in which actions are strategic substitutes (e.g., public good provision)., Comment: arXiv admin note: text overlap with arXiv:2305.07124

In this note, we propose a simple-looking but broad conjecture about star-algebras over the field of real numbers. The conjecture enables many matrix decompositions to be represented by star-algebras and star-ideals. This paper is written for people with a background in representation theory and module theory. The motivation for investigating this is the possibility of expressing polymorphic algorithms in numerical and theoretical linear algebra. This is similar to but different from algebraic (semiring based) approaches to dynamic programming. We prove certain cases of the conjecture.

We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrary digraphs, on oriented digraphs, and on symmetric digraphs. We demonstrate applications of the dichotomies for binary-action polymatrix games and several graph theory problems., Comment: arXiv admin note: substantial text overlap with arXiv:2305.07124

For a vertex $x$ of a digraph, $d^+(x)$ ($d^-(x)$, resp.) is the number of vertices at distance 1 from (to, resp.) $x$ and $d^{++}(x)$ is the number of vertices at distance 2 from $x$. In 1995, Seymour conjectured that for any oriented graph $D$ there exists a vertex $x$ such that $d^+(x)\leq d^{++}(x)$. In 2006, Sullivan conjectured that there exists a vertex $x$ in $D$ such that $d^-(x)\leq d^{++}(x)$. We give a sufficient condition in terms of the number of transitive triangles for an oriented graph to satisfy Sullivan's conjecture. In particular, this implies that Sullivan's conjecture holds for all orientations of planar graphs and of triangle-free graphs. An oriented graph $D$ is an oriented split graph if the vertices of $D$ can be partitioned into vertex sets $X$ and $Y$ such that $X$ is an independent set and $Y$ induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when $Y$ induces a regular or an almost regular tournament., Comment: 14 pages, 1 figures

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in the context of simple binary-action polymatrix games: (i) maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-maximizing Nash equilibrium. We introduce an intermediate, new graph-partition problem, termed Maximum Weighted Digraph Partition, which is of independent interest, and we provide a complexity dichotomy for it. This dichotomy, among other results, provides as a corollary a dichotomy for Objective (i) for general binary-action polymatrix games. In addition, it reveals that the complexity of achieving these objectives varies depending on the form of the coordination problem. Specifically, Objectives (i) and (ii) can be efficiently solved in pure-coordination games, but are NP-hard in anti-coordination games. Finally, we show that objective (iii) is NP-hard even for simple non-trivial pure-coordination games., Comment: 25 pages; A shortened version of this article has been accepted for presentation and publication at the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023)

Witnessing the advancing scale and complexity of chip design and benefiting from high-performance computation technologies, the simulation of Very Large Scale Integration (VLSI) Circuits imposes an increasing requirement for acceleration through parallel computing with GPU devices. However, the conventional parallel strategies do not fully align with modern GPU abilities, leading to new challenges in the parallelism of VLSI simulation when using GPU, despite some previous successful demonstrations of significant acceleration. In this paper, we propose a novel approach to accelerate 4-value logic timing-aware gate-level logic simulation using waveform-based GPU parallelism. Our approach utilizes a new strategy that can effectively handle the dependency between tasks during the parallelism, reducing the synchronization requirement between CPU and GPU when parallelizing the simulation on combinational circuits. This approach requires only one round of data transfer and hence achieves one-pass parallelism. Moreover, to overcome the difficulty within the adoption of our strategy in GPU devices, we design a series of data structures and tune them to dynamically allocate and store new-generated output with uncertain scale. Finally, experiments are carried out on industrial-scale open-source benchmarks to demonstrate the performance gain of our approach compared to several state-of-the-art baselines.

We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollobas, Gyafas, Lehel and Scott (J Graph Th 55(1) (2007)) for unweighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems.

Cartesian product networks are always regarded as a tool for ``combining'' two given networks with established properties to obtain a new one that inherits properties from both. For a graph $F=(V,E)$ and a set $S\subseteq V(F)$ of at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner tree connecting $S$} (or simply, \emph{an $S$-tree}) is a subgraph $T=(V',E')$ of $F$ that is a tree with $S\subseteq V'$. For $S\subseteq V(F)$ and $|S|\geq 2$, the {\it generalized local edge-connectivity} $\lambda(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $F$. For an integer $k$ with $2\leq k\leq n$, the {\it generalized $k$-edge-connectivity} $\lambda_k(F)$ of a graph $F$ is defined as $\lambda_k(F)=\min\{\lambda(S)\,|\,S\subseteq V(F) \ and \ |S|=k\}$.In this paper, we give sharp upper and lower bounds for $\lambda_k(G\Box H)$, where $\Box$ is the Cartesian product operation, and $G,H$ are two graphs., Comment: 14 pages; 3 figures

We present two interactive visualisations of 2x2 real matrices, which we call v1 and v2. v1 is only valid for PSD matrices, and uses the spectral theorem in a trivial way -- we use it as a warm-up. By contrast, v2 is valid for *all* 2x2 real matrices, and is based on the lesser known theory of Lie Sphere Geometry. We show that the dynamics of iterative eigenvalue algorithms can be illustrated using both. v2 has the advantage that it simultaneously depicts many properties of a matrix, all of which are relevant to the study of eigenvalue algorithms. Examples of the properties of a matrix that v2 can depict are its Jordan Normal Form and orthogonal similarity class, as well as whether it is triangular, symmetric or orthogonal. Despite its richness, using v2 interactively seems rather intuitive.

A graph $H$ is a clique graph if $H$ is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the $(a,d)$-{Cluster Editing} problem, where for fixed natural numbers $a,d$, given a graph $G$ and vertex-weights $a^*:\ V(G)\rightarrow \{0,1,\dots, a\}$ and $d^*{}:\ V(G)\rightarrow \{0,1,\dots, d\}$, we are to decide whether $G$ can be turned into a cluster graph by deleting at most $d^*(v)$ edges incident to every $v\in V(G)$ and adding at most $a^*(v)$ edges incident to every $v\in V(G)$. Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of $(a,d)$-{Cluster Editing} for all pairs $a,d$ apart from $a=d=1.$ Abu-Khzam (2017) conjectured that $(1,1)$-{Cluster Editing} is in P. We resolve Abu-Khzam's conjecture in affirmative by (i) providing a serious of five polynomial-time reductions to $C_3$-free and $C_4$-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving $(1,1)$-{Cluster Editing} on $C_3$-free and $C_4$-free graphs of maximum degree at most 3.

We present a simple functional programming language, called Dual PCF, that implements forward mode automatic differentiation using dual numbers in the framework of exact real number computation. The main new feature of this language is the ability to evaluate correctly up to the precision specified by the user -- in a simple and direct way -- the directional derivative of functionals as well as first order functions. In contrast to other comparable languages, Dual PCF also includes the recursive operator for defining functions and functionals. We provide a wide range of examples of Lipschitz functions and functionals that can be defined in Dual PCF. We use domain theory both to give a denotational semantics to the language and to prove the correctness of the new derivative operator using logical relations. To be able to differentiate functionals -- including on function spaces equipped with their compact-open topology that do not admit a norm -- we develop a domain-theoretic directional derivative that is Scott continuous and extends Clarke's subgradient of real-valued locally Lipschitz maps on Banach spaces to real-valued continuous maps on Hausdorff topological vector spaces. Finally, we show that we can express arbitrary computable linear functionals in Dual PCF., Comment: 19 pages, no figures, MFPS'23

We show that the spectral theorem -- which we understand to be a statement that every self-adjoint matrix admits a certain type of canonical form under unitary similarity -- admits analogues over other $*$-algebras distinct from the complex numbers. If these $*$-algebras contain nilpotents, then it is shown that there is a consistent way in which many classic matrix decompositions -- such as the Singular Value Decomposition, the Takagi decomposition, the skew-Takagi decomposition, and the Jordan decomposition, among others -- are immediate consequences of these. If producing the relevant canonical form of a self-adjoint matrix were a subroutine in some programming language, then the corresponding classic matrix decomposition would be a 1-line invocation with no additional steps. We also suggest that by employing operator overloading in a programming language, a numerical algorithm for computing a unitary diagonalisation of a complex self-adjoint matrix would generalise immediately to solving problems like SVD or Takagi. While algebras without nilpotents (like the quaternions) allow for similar unifying behaviour, the classic matrix decompositions which they unify are never obtained as easily. In the process of doing this, we develop some spectral theory over Clifford algebras of the form $\cl_{p,q,0}(\mathbb R)$ and $\cl_{p,q,1}(\mathbb R)$ where the former is admittedly quite easy. We propose a broad conjecture about spectral theorems.

We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is a guarantee on the value that any solution on $G$ takes. The goal is to design algorithms which find such solution in time whose complexity in $k$ is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems.

A {\em quasi-kernel} of a digraph $D$ is an independent set $Q\subseteq V(D)$ such that for every vertex $v\in V(D)\backslash Q$, there exists a directed path with one or two arcs from $v$ to a vertex $u\in Q$. In 1974, Chv\'{a}tal and Lov\'{a}sz proved that every digraph has a quasi-kernel. In 1976, Erd\H{o}s and S\'zekely conjectured that every sink-free digraph $D=(V(D),A(D))$ has a quasi-kernel of size at most $|V(D)|/2$. In this paper, we give a new method to show that the conjecture holds for a generalization of anti-claw-free digraphs. For any sink-free one-way split digraph $D$ of order $n$, when $n\geq 3$, we show a stronger result that $D$ has a quasi-kernel of size at most $\frac{n+3}{2} - \sqrt{n}$, and the bound is sharp., Comment: 14 pages

In this paper we consider stable matchings subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigned pairs are not, and, importantly, are stable. Our main contribution is an algorithm, based on the iterated deletion of unattractive alternatives, that determines if assignment constraints are compatible with stability. Whenever there is a stable matching that satisfies the assignment constraints, our algorithm outputs all of them (each in polynomial time per solution). This provides market designers with (i) a tool to test the feasibility of stable matchings subject to assignment constraints, and (ii) a tool to implement them when feasible.

We propose a new way of visualising the dynamics of iterative eigenvalue algorithms such as the QR algorithm, over the important special case of PSD (positive semi-definite) matrices. Many subtle and important properties of such algorithms are easily found this way. We believe that this may have pedagogical value to both students and researchers of numerical linear algebra. The fixed points of iterative algorithms are obtained visually, and their stability is analysed intuitively. It becomes clear that what it means for an iterative eigenvalue algorithm to "converge quickly" is an ambiguous question, depending on whether eigenvalues or eigenvectors are being sought. The presentation is likely a novel one, and using it, a theorem about the dynamics of general iterative eigenvalue algorithms is proved. There is an accompanying video series, currently hosted on Youtube, that has certain advantages in terms of fully exploiting the interactivity of the visualisation.

We introduce a novel approach of using important cuts which allowed us to design significantly faster fixed-parameter tractable (FPT) algorithms for the following routing problems: the Mixed Chinese Postman Problem parameterized by the number of directed edges (Gutin et al., JCSS 2017), the Minimum Shared Edges problem (MSE) parameterized by the number p of paths between two specified vertices (Fluschnik et al., JCSS 2019), and the Weighted Min Cut Prevention problem (Gruttemeier et al., WG 2021). The Minimum Vulnerability problem (MV) is a generalization of MSE (Assadi et al., Algorithmica 2014). The only known FPT algorithm for MV parameterized by p (the same parameter as for MSE) was for chordal graphs (Aoki et al., JCO 2018). We design an FPT algorithm for MV on all undirected graphs., Comment: There is an error in the proof of Lemma 4

Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $2\le k\leq n$. A strong subgraph $H$ of $D$ is called an $S$-strong subgraph if $S\subseteq V(H)$. A pair of $S$-strong subgraphs $D_1$ and $D_2$ are said to be arc-disjoint if $A(D_1)\cap A(D_2)=\emptyset$. Let $\lambda_S(D)$ be the maximum number of arc-disjoint $S$-strong subgraphs in $D$. The strong subgraph $k$-arc-connectivity is defined as $$\lambda_k(D)=\min\{\lambda_S(D)\mid S\subseteq V(D), |S|=k\}.$$ The parameter $\lambda_k(D)$ can be seen as a generalization of classical edge-connectivity of undirected graphs. In this paper, we first obtain a formula for the arc-connectivity of Cartesian product $\lambda(G\Box H)$ of two digraphs $G$ and $H$ generalizing a formula for edge-connectivity of Cartesian product of two undirected graphs obtained by Xu and Yang (2006). Then we study the strong subgraph 2-arc-connectivity of Cartesian product $\lambda_2(G\Box H)$ and prove that $ \min\left \{ \lambda \left ( G \right ) \left | H \right | , \lambda \left ( H \right ) \left |G \right |,\delta ^{+ } \left ( G \right )+ \delta ^{+ } \left ( H \right ),\delta ^{- } \left ( G \right )+ \delta ^{- } \left ( H \right ) \right \}\ge\lambda_2(G\Box H)\ge \lambda_2(G)+\lambda_2(H)-1.$ The upper bound for $\lambda_2(G\Box H)$ is sharp and is a simple corollary of the formula for $\lambda(G\Box H)$. The lower bound for $\lambda_2(G\Box H)$ is either sharp or almost sharp i.e. differs by 1 from the sharp bound. We also obtain exact values for $\lambda_2(G\Box H)$, where $G$ and $H$ are digraphs from some digraph families., Comment: arXiv admin note: text overlap with arXiv:1805.01687

An instance $I$ of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in $I$ is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a smallest perturbation of $I$. Boehmer et al. (2021) designed a polynomial-time algorithm to find the minimum number of swaps required to turn a given maximal matching into a stable matching. We generalize this result to the many-to-many version of SMP. We do so first by introducing a new representation of SMP as an extended bipartite graph and subsequently by reducing the problem to submodular minimization. It is a natural problem to establish the computational complexity of deciding whether at most $k$ swaps are enough to turn $I$ into an instance where one of the maximum matchings is stable. Using a hardness result of Gupta et al. (2020), we prove that this problem is NP-hard and, moreover, this problem parameterised by $k$ is W[1]-hard. We also obtain a lower bound on the running time for solving the problem using the Exponential Time Hypothesis.

We propose definitions of SVD, spectral decomposition (for self-adjoint matrices) and Jordan decomposition which make sense for all rings. For many rings, these decompositions can be shown to exist. For some specific rings, these decompositions are complicated to describe in full and prove the existence of. These decompositions have occurred piecemeal in the literature. We conjecture that they exist for many rings, including all Clifford algebras over the real numbers and complex numbers. The origin of this programme is not directly in module theory or linear algebra.

We prove the following new results. (a) Let $T$ be a regular tournament of order $2n+1\geq 11$ and $S$ a subset of $V(T)$. Suppose that $|S|\leq \frac{1}{2}(n-2)$ and $x$, $y$ are distinct vertices in $V(T)\setminus S$. If the subtournament $T-S$ contains an $(x,y)$-path of length $r$, where $3\leq r\leq |V(T)\setminus S|-2$, then $T-S$ also contains an $(x,y)$-path of length $r+1$. (b) Let $T$ be an $m$-irregular tournament of order $p$, i.e., $|d^+(x)-d^-(x)|\le m$ for every vertex $x$ of $T.$ If $m\leq \frac{1}{3}(p-5)$ (respectively, $m\leq \frac{1}{5}(p-3)$), then for every pair of vertices $x$ and $y$, $T$ has an $(x,y)$-path of any length $k$, $4\leq k\leq p-1$ (respectively, $3\leq k\leq p-1$ or $T$ belongs to a family $\cal G$ of tournaments, which is defined in the paper). In other words, (b) means that if the semidegrees of every vertex of a tournament $T$ of order $p$ are between $\frac{1}{3}(p+1)$ and $\frac{2}{3}(p-2)$ (respectively, between $\frac{1}{5}(2p-1)$ and $\frac{1}{5}(3p-4)$), then the claims in (b) hold. Our results improve in a sense related results of Alspach (1967), Jacobsen (1972), Alspach et al. (1974), Thomassen (1978) and Darbinyan (1977, 1978, 1979), and are sharp in a sense.

Let $D$ be a digraph and let $\lambda(D)$ denote the number of vertices in a longest path of $D$. For a pair of vertex-disjoint induced subdigraphs $A$ and $B$ of $D$, we say that $(A,B)$ is a partition of $D$ if $V(A)\cup V(B)=V(D).$ The Path Partition Conjecture (PPC) states that for every digraph, $D$, and every integer $q$ with $1\leq q\leq\lambda(D)-1$, there exists a partition $(A,B)$ of $D$ such that $\lambda(A)\leq q$ and $\lambda(B)\leq\lambda(D)-q.$ Let $T$ be a digraph with vertex set $\{u_1,\dots, u_t\}$ and for every $i\in [t]$, let $H_i$ be a digraph with vertex set $\{u_{i,j_i}\colon\, j_i\in [n_i]\}$. The {\em composition} $Q=T[H_1,\dots , H_t]$ of $T$ and $H_1,\ldots, H_t$ is a digraph with vertex set $\{u_{i,j_i}\colon\, i\in [t], j_i\in [n_i]\}$ and arc set $$A(Q)=\cup^t_{i=1}A(H_i)\cup \{u_{i,j_i}u_{p,q_p}\colon\, u_iu_p\in A(T), j_i\in [n_i], q_p\in [n_p]\}.$$ We say that $Q$ is acyclic {(semicomplete, respectively)} if $T$ is acyclic {(semicomplete, respectively)}. In this paper, we introduce a conjecture stronger than PPC using a property first studied by Bang-Jensen, Nielsen and Yeo (2006) and show that the stronger conjecture holds for wide families of acyclic and semicomplete compositions., Comment: 9 pages

In this paper, we study two types of strong subgraph packing problems in digraphs, including internally disjoint strong subgraph packing problem and arc-disjoint strong subgraph packing problem. These problems can be viewed as generalizations of the famous Steiner tree packing problem and are closely related to the strong arc decomposition problem. We first prove the NP-completeness for the internally disjoint strong subgraph packing problem restricted to symmetric digraphs and Eulerian digraphs. Then we get inapproximability results for the arc-disjoint strong subgraph packing problem and the internally disjoint strong subgraph packing problem. Finally we study the arc-disjoint strong subgraph packing problem restricted to digraph compositions and obtain some algorithmic results by utilizing the structural properties.