Arrow Research search

Author name cluster

Patrick Prosser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

JAIR Journal 2018 Journal Article

When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases

  • Ciaran McCreesh
  • Patrick Prosser
  • Christine Solnon
  • James Trimble

The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not. Although both variants are NP-complete, algorithms inspired by constraint programming can operate comfortably on many real-world problem instances with thousands of vertices. However, they cannot handle arbitrary instances of this size. We show how to generate "really hard" random instances for subgraph isomorphism problems, which are computationally challenging with a couple of hundred vertices in the target, and only twenty pattern vertices. For the non-induced version of the problem, these instances lie on a satisfiable / unsatisfiable phase transition, whose location we can predict; for the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. These results have practical consequences: we explain why the widely researched "filter / verify" indexing technique used in graph databases is founded upon a misunderstanding of the empirical hardness of NP-complete problems, and cannot be beneficial when paired with any reasonable subgraph isomorphism algorithm.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

A Partitioning Algorithm for Maximum Common Subgraph Problems

  • Ciaran McCreesh
  • Patrick Prosser
  • James Trimble

We introduce a new branch and bound algorithm for the maximum common subgraph and maximum common connected subgraph problems which is based around vertex labelling and partitioning. Our method in some ways resembles a traditional constraint programming approach, but uses a novel compact domain store and supporting inference algorithms which dramatically reduce the memory and computation requirements during search, and allow better dual viewpoint ordering heuristics to be calculated cheaply. Experiments show a speedup of more than an order of magnitude over the state of the art, and demonstrate that we can operate on much larger graphs without running out of memory.

PDF Details

SoCS Conference 2016 Conference Paper

Finding Maximum k-Cliques Faster Using Lazy Global Domination

  • Ciaran McCreesh
  • Patrick Prosser

A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem, although large sparse k-clique graphs reduce to large dense clique graphs, which can be computationally challenging. We adapt a state of the art maximum clique algorithm to show that this reduction is in fact useful in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs. We also use thread-parallel search to solve some harder instances.

Details

IJCAI Conference 2016 Conference Paper

Heuristics and Really Hard Instances for Subgraph Isomorphism Problems

  • Ciaran McCreesh
  • Patrick Prosser
  • James Trimble

We show how to generate "really hard'" random instances for subgraph isomorphism problems. For the non-induced variant, we predict and observe a phase transition between satisfiable and unsatisfiable instances, with a corresponding complexity peak seen in three different solvers. For the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. We also discuss variable and value ordering heuristics, and their relationship to the expected number of solutions.

PDF Details

IJCAI Conference 2013 Conference Paper

Breaking Symmetries in Graph Representation

  • Michael Codish
  • Alice Miller
  • Patrick Prosser
  • Peter J. Stuckey

There are many complex combinatorial problems which involve searching for an undirected graph satisfying a certain property. These problems are often highly challenging because of the large number of isomorphic representations of a possible solution. In this paper we introduce novel, effective and compact, symmetry breaking constraints for undirected graph search. While incomplete, these prove highly beneficial in pruning the search for a graph. We illustrate the application of symmetry breaking in graph representation to resolve several open instances in extremal graph theory.

PDF Details DOI

ICAPS Conference 2003 Conference Paper

Vehicle Routing and Job Shop Scheduling: What's the Difference?

  • J. Christopher Beck
  • Patrick Prosser
  • Evgeny Selensky

Despite a number of similarities, vehicle routing problems and scheduling problems are typically solved with different techniques. In this paper, we undertake a systematic study of problem characteristics that differ between vehicle routing and scheduling problems in order to identify those that are important for the performance of typical vehicle routing and scheduling techniques. In particular, we find that the addition of temporal constraints among visits or the addition of tight vehicle specialization constraints significantly improves the performance of scheduling techniques relative to vehicle routing techniques.

Details

AAAI Conference 1997 Conference Paper

The Scaling of Search Cost

  • Ian P. Gent
  • Patrick Prosser

We show that a resealed constrainedness parameter provides the basis for accurate numerical models of search cost for both backtracking and local search algorithms. In the past, the scaling of performance has been restricted to critically constrained problems at the phase transition. Here, we show how to extend models of search cost to the full width of the phase transition. This enables the direct comparison of algorithms on both under-constrained and overconstrained problems. We illustrate the generality of the approach using three different problem domains (satisfiability, constraint satisfaction and travelling salesperson problems) with both backtracking algorithms like the Davis-Putnam procedure and local search algorithms like GSAT. As well as modelling data from experiments, we give accurate predictions for results beyond the range of the experiments.

PDF Details

AIJ Journal 1996 Journal Article

An empirical study of phase transitions in binary constraint satisfaction problems

  • Patrick Prosser

An empirical study of randomly generated binary constraint satisfaction problems reveals that for problems with a given number of variables, domain size, and connectivity there is a critical level of constraint tightness at which a phase transition occurs. At the phase transition, problems change from being soluble to insoluble, and the difficulty of problems increases dramatically. A theory developed by Williams and Hogg [44], and independently developed by Smith [37], predicts where the hardest problems should occur. It is shown that the theory is in close agreement with the empirical results, except when constraint graphs are sparse.

Details DOI

AAAI Conference 1996 Conference Paper

The Constrainedness of Search

  • Ian P. Gent
  • Patrick Prosser

We introduce a parameter that measures the “constrainedness” of an ensemble of combinatorial problems. If problems are over-constrained, they are likely to be insoluble. If problems are under-constrained, they are likely to be soluble. This constrainedness parameter generalizes a number of parameters previously used in different NP-complete problem classes. Phase transitions in different NP classes can thus be directly compared. This parameter can also be used in a heuristic to guide search. The heuristic captures the intuition of making the most constrained choice first, since it is often useful to branch into the least constrained subproblem. Many widely disparate heuristics can be seen as minimizing constrainedness.

PDF Details