TL;DR
This paper tackles the computational complexity of evaluating the interlace polynomial, a graph invariant related to DNA sequencing and other combinatorial problems. The authors introduce novel graph transformations to prove that evaluating this polynomial is #P-hard across almost the entire parameter space, significantly advancing our understanding of its computational landscape.
What Problem Does This Paper Address?
The interlace polynomial, particularly its two-variable version $q(G; x, y)$, is a fascinating object with connections to various graph properties and even DNA sequencing. While the celebrated Tutte polynomial's complexity has been well-studied (known to be #P-hard almost everywhere), the interlace polynomial's computational landscape was less understood. Specifically, Arratia, Bollobás, and Sorkin (2004) posed a challenge: to determine the complexity of evaluating $q(G; x, y)$ at arbitrary points $(x, y)$. This paper aims to provide a comprehensive answer to this challenge, mapping out where the evaluation is computationally feasible and where it becomes intractable.
Methods
The core of this paper lies in the development of three new graph transformations: vertex cloning, adding combs, and adding cycles. These transformations are crucial because they allow the authors to relate the interlace polynomial of a graph to that of a modified graph. This is a key technique for proving complexity results: if evaluating a polynomial at point A is hard, and we can reduce evaluating it at point B to evaluating it at point A using a graph transformation, then evaluating at point B is also hard.
The authors use these transformations to establish point-to-point reductions. For instance, cloning a vertex $k-1$ times in a graph $G$ to create $G_k$ allows them to relate $P(G_k; u, x)$ to $P(G; u, (1+x)^k - 1)$. By carefully choosing $k$ and the parameters, they can map points in the parameter space to other points, effectively "spreading" the known hardness. They also leverage connections to the Tutte polynomial of planar graphs, using medial graphs and Euler circuits to establish #P-hardness for certain points.
Datasets
Not discussed in the paper. The paper focuses on theoretical graph properties and computational complexity rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Graph transformations as complexity tools: The paper demonstrates the power of graph transformations (cloning, combs, cycles) not just for defining graph polynomials but as fundamental tools for proving complexity bounds. This is a novel approach for the interlace polynomial, contrasting with the edge-based reductions used for the Tutte polynomial.
- Mapping the complexity landscape: The authors provide a near-complete picture of the computational complexity of the interlace polynomial $q(G; x, y)$ and its related polynomials (vertex-nullity, vertex-rank, independent set). They show that it's #P-hard almost everywhere, with only specific lines and points being computationally tractable.
- Bridging interlace and Tutte polynomials: The connection established between the interlace polynomial of certain graphs and the Tutte polynomial of their planar counterparts is a significant theoretical link, allowing the transfer of complexity results.
- Inapproximability of the independent set polynomial: Beyond exact evaluation, the paper shows that approximating the independent set polynomial (a specialization of the interlace polynomial) is also computationally hard, providing a strong negative result for approximation algorithms.
Key Results
- #P-hardness of $q(G; x, y)$: The two-variable interlace polynomial $q(G; x, y)$ is proven to be #P-hard to evaluate at almost every point $(x, y)$ in the plane. Tractable cases are limited to specific lines (e.g., $x=y$) and points.
- Specializations are also hard: Three important specializations – the vertex-nullity interlace polynomial, the vertex-rank interlace polynomial, and the independent set polynomial – are shown to be #P-hard to evaluate almost everywhere.
- Hardness of approximation: The independent set polynomial is shown to be hard to approximate within a certain factor, unless RP = NP.
- New graph transformations: The paper introduces and utilizes vertex cloning, adding combs, and adding cycles as effective tools for complexity reductions.
Limitations and Future Work
- Open complexity regions: While the paper covers most of the parameter space, there remain some "unknown" regions in the complexity map for $q(G; x, y)$ (indicated as gray in Figure 1) where the complexity is still open.
- Specific points: For some specializations like the vertex-rank interlace polynomial, there are still open questions about the complexity at specific points (e.g., $x=0, 1-\beta, 1+\beta$).
- Future work: The authors' work naturally opens avenues for exploring the remaining open complexity regions and potentially finding more connections between interlace polynomials and other graph invariants. The techniques developed could also be applied to other graph polynomials.
Summary updated