Source author record

Robert Crowston

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics math.CO

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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}$ .

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.

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)$ .

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}.

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$ .

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.

Robert Crowston

Research overview

Is this your work?

6 publications

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

Parameterizations of Test Cover with Bounded Test Sizes

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

Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound

Parameterized Complexity of MaxSat Above Average

Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

See the researcher in context

Building this map preview