# Mark Jones

## Contact Details

NameMark Jones |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Data Structures and Algorithms (20) Computer Science - Computational Complexity (10) Computer Science - Discrete Mathematics (8) Computer Science - Cryptography and Security (4) Mathematics - Combinatorics (4) Quantum Physics (2) Physics - Biological Physics (1) High Energy Physics - Phenomenology (1) Astrophysics (1) High Energy Physics - Experiment (1) |

## Publications Authored By Mark Jones

Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing {possibly discordant} evolutionary scenarios for a given set of genes or species, and aims at finding a single tree that minimizes the leaf-removal distance to the input trees. This problem is a specific instance of the general consensus/supertree problem, widely used to combine or summarize discordant evolutionary trees. Read More

Orthology and paralogy relations are often inferred by methods based on gene similarity, which usually yield a graph depicting the relationships between gene pairs. Such relation graphs are known to frequently contain errors, as they cannot be explained via a gene tree that both contains the depicted orthologs/paralogs, and that is consistent with a species tree $S$. This idea of detecting errors through inconsistency with a species tree has mostly been studied in the presence of speciation and duplication events only. Read More

We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes in the literature that use symmetric cryptographic primitives, each user is assigned a single secret and derives decryption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on a chain partition of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. Read More

A walk $W$ in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in $W$ is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type $i$ is a proper superset of graphs of acyclicity of type $i+1$, $i=1,2,3,4.$ The first three types are equivalent to the absence of PC cycles, PC trails, and PC walks, respectively. Read More

It is well-known that the Chinese postman problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in sharp contrast to the Chinese postman problem on mixed graphs, i. Read More

Let integers $r\ge 2$ and $d\ge 3$ be fixed. Let ${\cal G}_d$ be the set of graphs with no induced path on $d$ vertices. We study the problem of packing $k$ vertex-disjoint copies of $K_{1,r}$ ($k\ge 2$) into a graph $G$ from parameterized preprocessing, i. Read More

A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirements, such as separation-of-duty, impose constraints on which subsets of users may perform certain subsets of steps. Read More

The simple security property in an information flow policy can be enforced by encrypting data objects and distributing an appropriate secret to each user. A user derives a suitable decryption key from the secret and publicly available information. A chain-based enforcement scheme provides an alternative method of cryptographic enforcement that does not require any public information, the trade-off being that a user may require more than one secret. Read More

Cryptographic access control has been studied for over 30 years and is now a mature research topic. When symmetric cryptographic primitives are used, each protected resource is encrypted and only authorized users should have access to the encryption key. By treating the keys themselves as protected resources, it is possible to develop schemes in which authorized keys are derived from the keys explicitly assigned to the user's possession and publicly available information. Read More

In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$ ($G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern {\em et al.} (in press) and Gutin, Jones and Sheng (ESA 2014), respectively. Read More

In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph $G$ ($G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges was known to be fixed-parameter tractable using a simple argument. Solving an open question of van Bevern et al. Read More

In the Directed $k$-Chinese Postman Problem ($k$-DCPP), we are given a connected weighted digraph $G$ and asked to find $k$ non-empty closed directed walks covering all arcs of $G$ such that the total weight of the walks is minimum. Gutin, Muciaccia and Yeo (Theor. Comput. Read More

Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of {\lambda}-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < {\lambda} < 1 and {\lambda}-extendible property {\Pi}, any connected graph G on n vertices and m edges contains a spanning subgraph H in {\Pi} with at least {\lambda}m + (1-{\lambda})(n-1)/2 edges. The property of being bipartite is {\lambda}-extendible for {\lambda} = 1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max-Cut. Read More

One way to state the Load Coloring Problem (LCP) is as follows. Let $G=(V,E)$ be graph and let $f:V\rightarrow \{{\rm red}, {\rm blue}\}$ be a 2-coloring. An edge $e\in E$ is called red (blue) if both end-vertices of $e$ are red (blue). Read More

The \emph{Workflow Satisfiability Problem (WSP)} is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a \emph{plan} -- an assignment of tasks to authorized users -- such that all constraints are satisfied. Several bespoke algorithms have been constructed for solving the WSP, optimised to deal with constraints (business rules) of particular types. Read More

We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized complexity of {\sc Steiner Tree} parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of non-terminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs, and hence unlikely to be fixed parameter tractable FPT. Read More

In the {\sc Test Cover} problem we are given a hypergraph $H=(V, \mathcal{E})$ with $|V|=n, |\mathcal{E}|=m$, and we assume that $\mathcal{E}$ is a test cover, i.e. for every pair of vertices $x_i, x_j$, there exists an edge $e \in \mathcal{E}$ such that $|{x_i,x_j}\cap e|=1$. Read More

An oriented graph is a directed graph without directed 2-cycles. Poljak and Turz\'{i}k (1986) proved that every connected oriented graph $G$ on $n$ vertices and $m$ arcs contains an acyclic subgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ arcs. Raman and Saurabh (2006) gave another proof of this result and left it as an open question to establish the parameterized complexity of the following problem: does $G$ have an acyclic subgraph with least $\frac{m}{2}+\frac{n-1}{4}+k$ arcs, where $k$ is the parameter? We answer this question by showing that the problem can be solved by an algorithm of runtime $(12k)!n^{O(1)}$. Read More

We consider vectors from $\{0,1\}^n$. The weight of such a vector $v$ is the sum of the coordinates of $v$. The distance ratio of a set $L$ of vectors is ${\rm dr}(L):=\max \{\rho(x,y):\ x,y \in L\}/ \min \{\rho(x,y):\ x,y \in L,\ x\neq y\},$ where $\rho(x,y)$ is the Hamming distance between $x$ and $y$. Read More

We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erd\H{o}s bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size m/2 + (n-1)/4 + k in time 2^O(k)n^4, or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed several times over the past 15 years. Read More

In MaxSat, we are given a CNF formula $F$ with $n$ variables and $m$ clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let $r_1,.. Read More

In the problem {\sc Min-DESC}, we are given a digraph $D$ and an integer $k$, and asked if there exists a set $A'$ of at most $k$ arcs in $D$, such that if we remove the arcs of $A'$, in the resulting digraph every strong component is Eulerian. {\sc Min-DESC} is NP-hard; Cechl\'{a}rov\'{a} and Schlotter (IPEC 2010) asked if the problem is fixed-parameter tractable when parameterized by $k$. We consider the subproblem of{\sc Min-DESC} when $D$ is a tournament. Read More

Let F be a CNF formula with n variables and m clauses. F is 3-satisfiable if for any 3 clauses in F, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiable CNF formula at least 2/3 of its clauses can be satisfied by a truth assignment. Read More

In the {\sc Hitting Set} problem, we are given a collection $\cal F$ of subsets of a ground set $V$ and an integer $p$, and asked whether $V$ has a $p$-element subset that intersects each set in $\cal F$. We consider two parameterizations of {\sc Hitting Set} below tight upper bounds: $p=m-k$ and $p=n-k$. In both cases $k$ is the parameter. Read More

In the Max Lin-2 problem we are given a system $S$ of $m$ linear equations in $n$ variables over $\mathbb{F}_2$ in which Equation $j$ is assigned a positive integral weight $w_j$ for each $j$. We wish to find an assignment of values to the variables which maximizes the total weight of satisfied equations. This problem generalizes Max Cut. Read More

Using photometric data from the 2MASS and GLIMPSE catalogues, I investigate the incidence of mid-infrared excesses (~10 microns) of G and K stars of luminosity class III. In order to obtain a large sample size, stars are selected using a near-IR colour-magnitude diagram. Sources which are candidates for showing mid-IR excess are carefully examined and modelled to determined whether they are likely to be G/K giants. Read More

The endohedral fullerene Er3N@C80 shows characteristic 1.5 micron photoluminescence at cryogenic temperatures associated with radiative relaxation from the crystal-field split Er3+ 4I13/2 manifold to the 4I15/2 manifold. Previous observations of this luminescence were carried out by photoexcitation of the fullerene cage states leading to relaxation via the ionic states. Read More

Molecular structures appear to be natural candidates for a quantum technology: individual atoms can support quantum superpositions for long periods, and such atoms can in principle be embedded in a permanent molecular scaffolding to form an array. This would be true nanotechnology, with dimensions of order of a nanometre. However, the challenges of realising such a vision are immense. Read More

Experiment E04-113 at Jefferson Lab Hall C plans to measure the beam-target double-spin asymmetries in semi-inclusive deep-inelastic $\vec p(e, e^\prime h)X$ and $\vec d(e, e^\prime h)X$ reactions ($h=\pi^+, \pi^-, K^+$ or$K^-$) with a 6 GeV polarized electron beam and longitudinally polarized NH$_3$ and LiD targets. The high statistic data will allow a spin-flavor decomposition in the region of $x=0.12 \sim 0. Read More

In this paper we argue that the pattern of cell movements in the morphogenetic process known as convergent extension can be understood as a energy minimization process, provided the cell-cell adhesive energy has a certain kind of anisotropy. This single simple property is sufficient cause for the type of cell elongation, alignment, and intercalation of a cellular array that is the characteristic of convergent extension. We describe the type of anisotropy required. Read More