Morphing: Combining Structure and Randomness

AAAI 1999

TL;DR

This paper introduces "morphing," a flexible technique for smoothly transitioning between structured and random problem instances. By applying this method to various problems like graph coloring and the Traveling Salesperson Problem (TSP), the authors demonstrate how to systematically study the impact of structure and randomness on computational complexity, revealing surprising insights into problem hardness.

What Problem Does This Paper Address?

Many real-world problems aren't purely structured (like a perfect grid) nor completely random. They often lie somewhere in between, exhibiting a mix of regularities and unpredictable elements. Understanding how this blend of structure and randomness affects the difficulty of solving computational problems is a significant challenge. Traditional methods often study purely random or purely structured instances, making it hard to isolate the specific impact of varying degrees of structure or randomness. This paper aims to bridge this gap by providing a systematic way to explore this "in-between" space.

Methods

The core contribution is the introduction of a general mechanism called "morphing." Morphing allows for the creation of intermediate problem instances by blending two existing structures, S₁ and S₂, using a parameter 'p' that controls the degree of mixing. The paper defines three types of morphs:

  • Type A (Substructure Selection): For each substructure (e.g., graph edges, SAT clauses), it's chosen from S₁ with probability (1-p) and from S₂ with probability p.
  • Type B (Fractional Mixing): A fraction (1-p) of substructures are taken from S₁, and a fraction p from S₂. This is particularly useful for graphs, where it involves taking common edges and then a mix of remaining edges.
  • Type C (Linear Combination): For structures that support addition and scalar multiplication (like vectors or functions), the morph is computed as (1-p)S₁ + pS₂.

The authors then apply these morphing techniques to various problem domains, including graph coloring, SAT problems, and TSP, to study specific phenomena like "small-world" networks and the effect of asymmetry or dimensionality.

Datasets

The paper does not introduce new datasets but rather uses existing problem classes and benchmarks to demonstrate the morphing technique. These include:

  • Random Graphs: Used in conjunction with ring lattices for "small-world" studies.
  • 2+p-SAT problems: A known class studied by morphing between 2-SAT and 3-SAT.
  • DIMACS Satisfiability Benchmark: Used to analyze the topology of SAT problem encodings.
  • Symmetric and Asymmetric TSP instances: Generated by morphing distance matrices.
  • 2D and 3D TSP instances: Created by morphing coordinate vectors.

Key Insights and Ideas

  • "Small-world" networks are a sweet spot for difficulty: The paper shows that graphs with a specific balance of structure (high clustering) and randomness (short path lengths) – the "small-world" phenomenon – can be particularly challenging for search algorithms. This peak difficulty occurs at a specific morphing ratio.
  • Asymmetry can simplify TSP: Introducing asymmetry into TSP distance matrices, even slightly, dramatically reduces the search cost to find the optimal tour. This suggests that symmetry, while intuitive, can make problems harder by increasing non-determinism.
  • Dimensionality impacts TSP difficulty: Increasing the dimensionality of TSP problems (from 2D to 3D) tends to make the optimal tour easier to find, possibly by increasing the variance in inter-city distances and making the optimal path more obvious.
  • Morphing offers a controlled way to study problem hardness: The technique provides a "dial" to systematically explore how varying degrees of structure and randomness influence computational complexity, offering advantages over studying purely random or purely structured instances.
  • Local vs. Complete Search Behavior: The study reveals that local search algorithms (like WalkSAT) perform better on more random instances, while complete search algorithms (like SATZ) struggle with highly random instances but can handle some structured ones more easily. This suggests a potential for portfolio approaches combining different search strategies.

Key Results

  • Graph Coloring: For "small-world" graphs generated by morphing a ring lattice and a random graph, the search cost (measured by flips for WalkSAT and nodes visited for SATZ) peaks at a specific morphing ratio, indicating a region of maximal difficulty.
  • TSP:
    • Introducing asymmetry into TSP distance matrices reduced search cost by orders of magnitude, while the optimal tour length only decreased slightly.
  • Increasing TSP dimensionality from 2D to 3D led to a drop in search cost, suggesting 3D problems are easier to solve.
  • SAT Encoding: The constraint graphs of many SAT benchmark problems exhibit "small-world" properties, suggesting that good encodings for search might naturally preserve or even emphasize topological structure.
  • Quasigroups: Morphing quasigroups with random graphs showed that while small-world properties decrease, coloring costs can increase, suggesting other factors beyond small-worldness contribute to problem hardness.

Limitations and Future Work

  • Generalizability of "Small-World" Difficulty: While the paper shows a peak in difficulty for graph coloring at a specific "small-world" morphing ratio, the exact location and nature of this peak might vary depending on the problem and the specific morphing parameters.
  • Portfolio Optimization: The paper suggests that combining local and complete search algorithms could improve overall performance and robustness. However, determining the optimal mix of algorithms for such portfolios requires further investigation.
  • Conjecture on Encodings: The paper conjectures that good SAT encodings preserve topological structure. Further work could rigorously prove or disprove this.
  • Exploration of Other Problems: The authors predict that morphing will find many other uses, implying future work could apply this technique to a wider range of computational problems.

Summary updated

BibTeX
@inproceedings{1999morphing,
  title = {{Morphing: Combining Structure and Randomness}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure