BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mark Jones

Mark Jones appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsmath.COCryptography and Securityphysics.ins-detnucl-ex

Catalog footprint

What is connected

29works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

29 published item(s)

preprint2026arXiv

The BigBite Calorimeter for the Super Bigbite Spectrometer Program at Jefferson Lab

We report features of the design, construction, installation, and performance of the BigBite Calorimeter (BBCal), a lead-glass electromagnetic calorimeter constructed as part of the BigBite Spectrometer (BBS), which served as the electron arm for the Super Bigbite Spectrometer (SBS) program of high-precision neutron electromagnetic form factor measurements in Hall A at Jefferson Lab. As a total-absorption calorimeter, BBCal provided the primary electron trigger for BBS, detecting (quasi-) elastically scattered electrons in the 1-4 GeV energy range with an energy resolution of approximately 6.2%, position resolution of 1.2 cm, and timing resolution of 0.5 ns.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Consistency of orthology and paralogy constraints in the presence of gene transfers

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. In this work, we ask: could the given set of relations be consistent if we allow lateral gene transfers in the evolutionary model? We formalize this question and provide a variety of algorithmic results regarding the underlying problems. Namely, we show that deciding if a relation graph $R$ is consistent with a given species network $N$ is NP-hard, and that it is W[1]-hard under the parameter "minimum number of transfers". However, we present an FPT algorithm based on the degree of the $DS$-tree associated with $R$. We also study analogous problems in the case that the transfer highways on a species tree are unknown.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Performance of photosensors in a high-rate environment for gas Cherenkov detectors

The solenoidal large intensity device (SoLID) at Jefferson Lab will push the boundaries of luminosity for a large-acceptance detector, which necessitates the use of a light-gas threshold Cherenkov counter for online event selection. Due to the high luminosity, the single-photon background rate in this counter can exceed 160 kHz/cm$^2$ at the photosensors. Therefore, it is essential to validate the high-rate limits of the planned photosensors and readout electronics in order to mitigate the risk of failure. We report on the design and an early set of studies carried out using a small telescopic Cherenkov device in a high-rate environment up to 60 kHz/cm$^2$, in Hall C at Jefferson Lab. Commercially available multi-anode photomultipliers (MaPMT) and low-cost large-area picosecond photodetectors (LAPPD) were tested using the JLab FADC250 modules for readout. The test beam results show that the MaPMT array and the internal stripline LAPPD can detect and identify single-electron and pair-production events in high-rate environments. Due to its higher quantum efficiency, the MaPMT array provided a better separation between the single-electron and the pair-production events compared to the internal stripline LAPPD. A GEANT4 simulation confirms the experimental performance of our telescopic device.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Unifying Characterization of Tree-based Networks and Orchard Networks using Cherry Covers

Phylogenetic networks are used to study evolutionary relationships between species in biology. Such networks are often categorized into classes by their topological features, which stem from both biological and computational motivations. We study two network classes in this paper: tree-based networks and orchard networks. Tree-based networks are those that can be obtained by inserting edges between the edges of an underlying tree. Orchard networks are a recently introduced generalization of the class of tree-child networks. Structural characterizations have already been discovered for tree-based networks; this is not the case for orchard networks. In this paper, we introduce cherry covers---a unifying characterization of both network classes---in which we decompose the edges of the networks into so-called cherry shapes and reticulated cherry shapes. We show that cherry covers can be used to characterize the class of tree-based networks as well as the class of orchard networks. Moreover, we also generalize these results to non-binary networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm

Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by establishing a linear kernel i.e., that after applying certain reduction rules the resulting instance has size that is bounded by a linear function of the distance. As powerful corollaries to this result we prove that the problem permits a polynomial-time constant-factor approximation algorithm; that the treewidth of a natural auxiliary graph structure encountered in phylogenetics is bounded by a function of the distance; and that the distance is within a constant factor of the size of a maximum agreement forest of the two trees, a well studied object in phylogenetics.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Not all phylogenetic networks are leaf-reconstructible

Unrooted phylogenetic networks are graphs used to represent evolutionary relationships. Accurately reconstructing such networks is of great relevance for evolutionary biology. It has recently been conjectured that all phylogenetic networks with at least five leaves can be uniquely reconstructed from their subnetworks obtained by deleting a single leaf and suppressing degree-2 vertices. Here, we show that this conjecture is false, by presenting a counter example for each possible number of leaves that is at least~4. Moreover, we show that the conjecture is still false when restricted to binary networks.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Exploring the tiers of rooted phylogenetic network space using tail moves

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rNNI (rooted Nearest Neighbour Interchange) and rSPR (rooted Subtree Prune and Regraft). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail-moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Acyclicity in Edge-Colored Graphs

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. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Cryptographic Enforcement of Information Flow Policies without Public Information via Tree Partitions

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. In general, many different chain partitions exist for the same policy and, until now, it was not known how to compute an appropriate one. In this paper, we introduce the notion of a tree partition, of which chain partitions are a special case. We show how a tree partition may be used to define a cryptographic enforcement scheme and prove that such schemes can be instantiated in such a way as to preserve the strongest security properties known for cryptographic enforcement schemes. We establish a number of results linking the amount of secret material that needs to be distributed to users with a weighted acyclic graph derived from the tree partition. These results enable us to develop efficient algorithms for deriving tree and chain partitions that minimize the amount of secret material that needs to be distributed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Parameterized Complexity of the $k$-Arc Chinese Postman Problem

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., we prove that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. Our proof is more involved and, in particular, uses a well-known result of Marx, O'Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cryptographic Enforcement of Information Flow Policies without Public Information

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. It has been generally assumed that each user would be assigned a single key from which all other authorized keys would be derived. Recent work has challenged this assumption by developing schemes that do not require public information, the trade-off being that a user may require more than one key. However, these new schemes, which require a chain partition of the partially ordered set on which the access control policy is based, have some disadvantages. In this paper we define the notion of a tree-based cryptographic enforcement scheme, which, like chain-based schemes, requires no public information. We establish that the strong security properties of chain-based schemes are preserved by tree-based schemes, and provide an efficient construction for deriving a tree-based enforcement scheme from a given policy that minimizes the number of keys required.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Linear-Vertex Kernel for the Problem of Packing $r$-Stars into a Graph without Long Induced Paths

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.e., kernelization, point of view. We show that every graph $G\in {\cal G}_d$ can be reduced, in polynomial time, to a graph $G'\in {\cal G}_d$ with $O(k)$ vertices such that $G$ has at least $k$ vertex-disjoint copies of $K_{1,r}$ if and only if $G'$ has. Such a result is known for arbitrary graphs $G$ when $r=2$ and we conjecture that it holds for every $r\ge 2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Workflow Satisfiability Problem with Class-Independent Constraints

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. The \emph{workflow satisfiability problem} (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies all such authorizations and constraints. An algorithm for solving WSP is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Given the computational difficulty of WSP, it is important, particularly for the second application, that such algorithms are as efficient as possible. We introduce class-independent constraints, enabling us to model scenarios where the set of users is partitioned into groups, and the identities of the user groups are irrelevant to the satisfaction of the constraint. We prove that solving WSP is fixed-parameter tractable (FPT) for this class of constraints and develop an FPT algorithm that is useful in practice. We compare the performance of the FPT algorithm with that of SAT4J (a pseudo-Boolean SAT solver) in computational experiments, which show that our algorithm significantly outperforms SAT4J for many instances of WSP. User-independent constraints, a large class of constraints including many practical ones, are a special case of class-independent constraints for which WSP was proved to be FPT (Cohen {\em et al.}, J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixed-parameter tractability of WSP.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Constructions for Chain-based Cryptographic Enforcement of Information Flow Policies

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. For a given information flow policy, there will be many different possible chain-based enforcement schemes. In this paper, we provide a polynomial-time algorithm for selecting a chain-based scheme which uses the minimum possible number of keys. We also compute the number of secrets that will be required and establish an upper bound on the number of secrets required by any user.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Structural Parameterizations of the Mixed Chinese Postman Problem

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. In this paper, we consider the unweighted version of MCPP. Solving an open question of van Bevern {\em et al.} (in press), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side, we show that the unweighted version of MCPP parameterized by tree-depth is fixed-parameter tractable. We are unaware of any natural graph parameters between pathwidth and tree-depth and so our results provide a dichotomy of the complexity of MCPP. Furthermore, we believe that MCPP is the first problem known to be W[1]-hard with respect to treewidth but FPT with respect to tree-depth.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Iterative Plan Construction for the Workflow Satisfiability Problem

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. It is natural to see the WSP as a subclass of the {\em Constraint Satisfaction Problem (CSP)} in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive as a CSP is that we can assume that the number of tasks is very small compared to the number of users. This is in sharp contrast with traditional CSP models where the domain is small and the number of variables is very large. As such, it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. We have identified a new FPT constraint language, user-independent constraint, that includes many of the constraints of interest in business processing systems. We are also able to prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. In this paper we present our generic algorithm, in which plans are grouped into equivalence classes, each class being associated with a \emph{pattern}. We demonstrate that our generic algorithm has running time $O^*(2^{k\log k})$, where $k$ is the number of tasks, for the language of user-independent constraints. We also show that there is no algorithm of running time $O^*(2^{o(k\log k)})$ for user-independent constraints unless the Exponential Time Hypothesis fails.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parameterized Algorithms for Load Coloring Problem

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). For a 2-coloring $f$, let $r'_f$ and $b'_f$ be the number of red and blue edges and let $μ_f(G)=\min\{r'_f,b'_f\}$. Let $μ(G)$ be the maximum of $μ_f(G)$ over all 2-colorings. We introduce the parameterized problem $k$-LCP of deciding whether $μ(G)\ge k$, where $k$ is the parameter. We prove that this problem admits a kernel with at most $7k$. Ahuja et al. (2007) proved that one can find an optimal 2-coloring on trees in polynomial time. We generalize this by showing that an optimal 2-coloring on graphs with tree decomposition of width $t$ can be found in time $O^*(2^t)$. We also show that either $G$ is a Yes-instance of $k$-LCP or the treewidth of $G$ is at most $2k$. Thus, $k$-LCP can be solved in time $O^*(4^k).$

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parameterized Directed $k$-Chinese Postman Problem and $k$ Arc-Disjoint Cycles Problem on Euler Digraphs

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. Sci. 513 (2013) 124--128) asked for the parameterized complexity of $k$-DCPP when $k$ is the parameter. We prove that the $k$-DCPP is fixed-parameter tractable. We also consider a related problem of finding $k$ arc-disjoint directed cycles in an Euler digraph, parameterized by $k$. Slivkins (ESA 2003) showed that this problem is W[1]-hard for general digraphs. Generalizing another result by Slivkins, we prove that the problem is fixed-parameter tractable for Euler digraphs. The corresponding problem on vertex-disjoint cycles in Euler digraphs remains W[1]-hard even for Euler digraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Max-Cut Parameterized Above the Edwards-Erdős Bound

We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erdő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. Our algorithm is asymptotically optimal, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Parameterizations of Test Cover with Bounded Test Sizes

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$. The objective is to find a minimum subset of $\mathcal{E}$ which is a test cover. The problem is used for identification across many areas, and is NP-complete. From a parameterized complexity standpoint, many natural parameterizations of {\sc Test Cover} are either $W[1]$-complete or have no polynomial kernel unless $coNP\subseteq NP/poly$, and thus are unlikely to be solveable efficiently. However, in practice the size of the edges is often bounded. In this paper we study the parameterized complexity of {\sc Test-$r$-Cover}, the restriction of {\sc Test Cover} in which each edge contains at most $r \ge 2$ vertices. In contrast to the unbounded case, we show that the following below-bound parameterizations of {\sc Test-$r$-Cover} are fixed-parameter tractable with a polynomial kernel: (1) Decide whether there exists a test cover of size $n-k$, and (2) decide whether there exists a test cover of size $m-k$, where $k$ is the parameter. In addition, we prove a new lower bound $\lceil \frac{2(n-1)}{r+1} \rceil$ on the minimum size of a test cover when the size of each edge is bounded by $r$. {\sc Test-$r$-Cover} parameterized above this bound is unlikely to be fixed-parameter tractable; in fact, we show that it is para-NP-complete, as it is NP-hard to decide whether an instance of {\sc Test-$r$-Cover} has a test cover of size exactly $\frac{2(n-1)}{r+1}$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Polynomial Kernels for λ-extendible Properties Parameterized Above the Poljak-Turzík Bound

Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < λ < 1 and λ-extendible property Π, any connected graph G on n vertices and m edges contains a spanning subgraph H in Π with at least λm + (1-λ)(n-1)/2 edges. The property of being bipartite is λ-extendible for λ = 1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max-Cut. Other examples of λ-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some integer q. Mnich et. al. (FSTTCS 2012) defined the closely related notion of strong λ-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly λ-extendible property Π is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound - does there exist a spanning subgraph H of a connected graph G such that H in Π and H has at least λm + (1-λ)(n-1)/2 + k edges? - subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when λ = 1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application

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. We improve this result by showing that every 3-satisfiable CNF formula F contains a subset of variables U, such that some truth assignment $τ$ will satisfy at least $2m/3+ m_U/3+ρn'$ clauses, where m is the number of clauses of F, m_U is the number of clauses of F containing a variable from U, n' is the total number of variables in clauses not containing a variable in U, and ρis a positive absolute constant. Both U and $τ$ can be found in polynomial time. We use our result to show that the following parameterized problem is fixed-parameter tractable and, moreover, has a kernel with a linear number of variables. In 3-S-MAXSAT-AE, we are given a 3-satisfiable CNF formula F with m clauses and asked to determine whether there is an assignment which satisfies at least 2m/3 + k clauses, where k is the parameter.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound

An oriented graph is a directed graph without directed 2-cycles. Poljak and Turzí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)}$. Thus, the problem is fixed-parameter tractable. We also prove that there is a polynomial time algorithm that either establishes that the input instance of the problem is a Yes-instance or reduces the input instance to an equivalent one of size $O(k^2)$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances

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 \{ρ(x,y):\ x,y \in L\}/ \min \{ρ(x,y):\ x,y \in L,\ x\neq y\},$ where $ρ(x,y)$ is the Hamming distance between $x$ and $y$. We prove that (a) for every constant $λ>1$ there are no positive constants $α$ and $C$ such that every set $K$ of at least $λ^p$ vectors with weight $p$ contains a subset $K'$ with $|K'|\ge |K|^α$ and ${\rm dr}(K')\le C$, % even when $|K|\ge λ$, (b) For a set $K$ of vectors with weight $p$, and a constant $C>2$, there exists $K'\subseteq K$ such that ${\rm dr}(K')\le C$ and $|K'| \ge |K|^α$, where $α= 1/ \lceil \log(p/2)/\log(C/2) \rceil$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Parameterized Complexity of Directed Steiner Tree on Sparse Graphs

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. The undirected {\sc Steiner Tree} problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for {\sc Directed Steiner Tree} (DST) on sparse graphs parameterized by the number of non-terminals in the solution tree. Specifically, we show that the problem is fixed parameter tractable on graphs excluding a topological minor, but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is required to be acyclic then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for {\sc Dominating Set} on sparse undirected graphs. These algorithms are asymptotically optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems

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. We prove that the first parameterization is fixed-parameter tractable, but has no polynomial kernel unless coNP$\subseteq$NP/poly. The second parameterization is W[1]-complete, but the introduction of an additional parameter, the degeneracy of the hypergraph $H=(V,{\cal F})$, makes the problem not only fixed-parameter tractable, but also one with a linear kernel. Here the degeneracy of $H=(V,{\cal F})$ is the minimum integer $d$ such that for each $X\subset V$ the hypergraph with vertex set $V\setminus X$ and edge set containing all edges of $\cal F$ without vertices in $X$, has a vertex of degree at most $d.$ In {\sc Nonblocker} ({\sc Directed Nonblocker}), we are given an undirected graph (a directed graph) $G$ on $n$ vertices and an integer $k$, and asked whether $G$ has a set $X$ of $n-k$ vertices such that for each vertex $y\not\in X$ there is an edge (arc) from a vertex in $X$ to $y$. {\sc Nonblocker} can be viewed as a special case of {\sc Directed Nonblocker} (replace an undirected graph by a symmetric digraph). Dehne et al. (Proc. SOFSEM 2006) proved that {\sc Nonblocker} has a linear-order kernel. We obtain a linear-order kernel for {\sc Directed Nonblocker}.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Parameterized Complexity of MaxSat Above Average

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,..., r_m$ be the number of literals in the clauses of $F$. Then $asat(F)=\sum_{i=1}^m (1-2^{-r_i})$ is the expected number of clauses satisfied by a random truth assignment (the truth values to the variables are distributed uniformly and independently). It is well-known that, in polynomial time, one can find a truth assignment satisfying at least $asat(F)$ clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least $asat(F)+k$ clauses, where $k$ is the parameter. We prove that MaxSat-AA is para-NP-complete and, thus, MaxSat-AA is not fixed-parameter tractable unless P$=$NP. This is in sharp contrast to MaxLin2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (arXiv:1104.1135v3). In fact, we consider a more refined version of {\sc MaxSat-AA}, {\sc Max-$r(n)$-Sat-AA}, where $r_j\le r(n)$ for each $j$. Alon {\em et al.} (SODA 2010) proved that if $r=r(n)$ is a constant, then {\sc Max-$r$-Sat-AA} is fixed-parameter tractable. We prove that {\sc Max-$r(n)$-Sat-AA} is para-NP-complete for $r(n)=\lceil \log n\rceil.$ We also prove that assuming the exponential time hypothesis, {\sc Max-$r(n)$-Sat-AA} is not in XP already for any $r(n)\ge \log \log n +ϕ(n)$, where $ϕ(n)$ is any unbounded strictly increasing function. This lower bound on $r(n)$ cannot be decreased much further as we prove that {\sc Max-$r(n)$-Sat-AA} is (i) in XP for any $r(n)\le \log \log n - \log \log \log n$ and (ii) fixed-parameter tractable for any $r(n)\le \log \log n - \log \log \log n - ϕ(n)$, where $ϕ(n)$ is any unbounded strictly increasing function. The proof uses some results on {\sc MaxLin2-AA}.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

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árová 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. We show that this problem is fixed-parameter tractable with respect to $k$.

0 citations0 reviewsNo code linkedOpen access