PaperlayerView exact revision on arXiv

Source-linked AI summary

Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time

Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams

arXiv:2610.22133v1cs.DS

TL;DR

Kratsch and Spinrad’s structural graph problems had intermediate-time algorithms and conditional n^ω−o(1) lower bounds, leaving their true complexity unresolved. This paper gives deterministic ˜O(n^ω)-time algorithms for those problems and partial progress on related problems. Under the stated hardness hypotheses, the main algorithms are optimal.

  • Problem

    It remained open whether Kratsch and Spinrad’s problems require intermediate time or admit ˜O(n^ω)-time algorithms despite conditional n^ω−o(1) lower bounds.

    Source: §1 · p. 2

  • Method

    The paper develops deterministic algorithms, including an induced-subgraph component algorithm based on a rectangular Boolean matrix multiplication equivalence.

    Source: Our Results · p. 4

  • Results

    All problems studied by Kratsch and Spinrad admit ˜O(n^ω)-time algorithms; the paper also improves decremental Simplicial Vertex to O(n^2.5275).

    Source: Our Results · p. 4

  • Takeaways & Limitations

    Under the hypotheses that n-dimensional OV, Simplicial Vertex, and Triangle Detection require n^ω−o(1) time, the main algorithms are optimal.

    Source: Our Results · p. 4

    For two related structural graph problems, the paper reports only partial progress, suspects their complexity may exceed O(n^ω), and leaves them open.

    Source: Our Results · p. 5

Abstract

from arXiv · show

In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained complexity, both from the upper- and lower-bound side: * From the upper-bound side, for each of these problems the authors give an intermediate running time strictly between $n^{\omega}$ and $n^3$, where $\omega<2.371177$ is the matrix multiplication exponent. When optimized, this running time can be made $\tilde{\mathcal{O}}(n^{(3+\omega)/2})$. By now, many more problems can be solved in this running time: directed unweighted or node-weighted APSP, a variety of matrix products such as max-min and dominance, RNA Folding and many more. For some of these, the community has also developed tools suggesting that this intermediate running time is necessary. * From the lower-bound side, the authors give lower bounds of $n^{\omega-o(1)}$, conditioned on three natural hardness hypotheses on the complexity of quantified variants of triangle detection that account for different types of hardness of such problems. Despite this, it has remained open for over 20 years which of these two pieces of evidence reflects the truth for the problems that Kratsch and Spinrad study: whether the intermediate running time is indeed necessary and stronger lower bounds hold, or whether the hardness evidence of Kratsch and Spinrad is essentially tight. In this paper, we resolve this question and show that the latter is the case: all problems admit an $\tilde{\mathcal{O}}(n^{\omega})$ time algorithm. As an additional contribution, we make partial algorithmic progress on further problems in structural graph theory of intermediate complexity, improving over previous work [Chiu and Lu, STACS 2022 and Information and Computation 2024][Spinrad, Discrete Applied Math 2004].

1 Introduction

Kratsch and Spinrad’s structural graph problems have resisted improvement for more than 20 years, leaving open whether their intermediate running times are necessary or whether they admit matrix-multiplication-time algorithms. This paper resolves that question for the journal-version problems and also reports partial progress on related problems.

1 Introduction

  • The open question was whether the studied problems require intermediate time or can be solved in ˜O(n^ω), despite their existing subcubic algorithms and conditional n^ω−o(1) lower bounds.Kratsch and Spinrad’s algorithms were optimized to ˜O(n^(3+ω)/2).Source: §1 · p. 2

1.1 The problems studied by Kratsch and Spinrad

  • Kratsch and Spinrad studied neighborhood-deleted components, extremities, star- and clique-cutsets, AT-free recognition, dominating pairs, and two-pairs in undirected graphs.These include component, recognition, cutset, and vertex-pair problems in structural graph theory.Source: §1.1 · pp. 2–3

1.2 Why 𝑛𝜔seems needed for all the problems

  • Three proposed sources of n^ω−o(1) hardness are Triangle Detection, Dominated Vertex (equivalent to high-dimensional OV), and Simplicial Vertex.The paper relates these sources to different quantifications: ∃∃∃, ∃∃∀, and ∃∀∀, respectively.Source: §1.2 · pp. 3–4

Our Results

  • The paper shows that all problems studied by Kratsch and Spinrad admit ˜O(n^ω)-time algorithms and are not intermediate; under the stated hardness hypotheses, these algorithms are optimal.The hypotheses concern n-dimensional OV, Simplicial Vertex, and Triangle Detection.Source: Our Results · p. 4
  • The induced subgraph connected component problem computes components of G[S] for each set S, and is equivalent to neighborhood-deleted components when |S|=Θ(n).The equivalence in the reverse direction uses a clique with one vertex per set, adjacent to vertices outside that set.Source: Our Results · p. 4
  • A deterministic ˜O(MM(|S|, n, n))-time algorithm solves the induced subgraph connected component problem, which yields ˜O(n^ω)-time algorithms for neighborhood-deleted components, extremities, star-cutsets, and fixed-pair two-pair testing.The stated running time is for an n-node input graph and non-empty set family S.Source: Our Results · pp. 4–5
  • The paper leaves two related problems open: it suspects their complexity may exceed O(n^ω), while improving decremental Simplicial Vertex to O(n^2.5275).The related problems include induced non-shortest paths and quasi-triangulated graph recognition.Source: Our Results · pp. 5–6
  • For any k≥3, an algorithm detecting a uv-trail between vertices at distance k in time T=Ω(n²) would give a triangle-detection algorithm in O(T) time.The paper describes this as evidence that matrix multiplication may be necessary even for a single pair at distance 3.Source: Our Results · p. 5

2 Overview

This overview presents three matrix-multiplication-time algorithms and the structural observations behind them. It also identifies open questions about robust linear-time algorithms and extensions of asteroidal-triple detection.

2.1 Induced Subgraph Connected Components in Matrix Multiplication Time

  • Connected components of every induced subgraph can be computed by repeatedly merging adjacent parts, with Boolean matrix multiplication finding inter-part edges.Parts grow to connected components within O(log n) rounds; the overview describes a derandomized version.Source: §2.1 · p. 7

2.2 Recognizing AT-free Graphs in Matrix Multiplication Time

  • For AT recognition, retaining one representative of each distinct neighborhood-deleted component preserves whether the constructed graph contains a triangle.The prior construction has O(n^2) edges and yields an O(n^2.81)-time approach; AT-free graphs have only O(n log n) distinct components.Source: §2.2 · pp. 8–9
  • AT-free graphs have at most 400 n log n distinct neighborhood-deleted components across all G_x.This bound supports reducing recognition to triangle detection on a smaller graph.Source: §2.2 · p. 9

2.3 Listing Dominating Pairs in Matrix Multiplication Time

  • Dominating-pair listing finds non-dominating pairs witnessed by each G_x component, using largest components and repeated witnesses from smaller ones.The largest component of each G_x can be processed in O(n^ω) time; smaller witnesses are handled by sampling nodes, with a derandomized version in the full proof.Source: §2.3 · pp. 9–10

Open Problems

  • Open questions include robust linear-time dominating-pair search on AT-free graphs and whether all-edge asteroidal-triple detection admits O(n^ω) time.The paper also points to fine-grained study of other structural graph problems.Source: Open Problems · p. 10

3 Preliminaries

The preliminaries fix graph and set notation, then provide tools for matrix-product witnesses and deterministic component fingerprints.

Graph and set notation

  • The graph notation defines neighborhoods, closed neighborhoods, graphs with a closed neighborhood removed, their connected components, and paths avoiding a set.The interval notation [i..j] includes both endpoints, while [i..j) excludes j.Source: §3 · p. 10

Matrix Multiplication and Witnesses

  • Boolean matrix multiplication can report one witness index for every nonzero product entry in deterministic near-matrix-multiplication time.For entry (i,j), the witness k satisfies A[i,k] = 1 and B[k,j] = 1.Source: §3 · p. 11

Deterministic Fingerprints for Partitions

  • Deterministic fingerprints identify partition sets uniquely across k partitions in O(nk log(nk)) time.Equal fingerprints correspond exactly to equal sets, and the construction uses O(nk) possible fingerprint values.Source: §3 · p. 11

4 Proofs

The proofs develop algorithms and bounds for induced-subgraph connected components, AT-free and quasi-triangulated graph recognition, listing dominating pairs and two-pairs, and decremental simplicial-vertex processing. They also reduce triangle detection to finding a uv-trail and analyze bounds on component counts and update costs.

4.1 Induced Subgraph Connected Components in Matrix Multiplication Time

  • Induced-subgraph connected components for a non-empty family S can be computed deterministically in O~(MM(|S|, n, n)) time.The algorithm uses union-find and runs Θ(log n) rounds of witness-finding and merges; after these rounds, each maintained set is a connected component.Source: §4.1 · pp. 11–12
  • The induced-subgraph connected-component problem encodes Boolean matrix multiplication: an instance on a 2n-node graph with |S| = s yields AB.The construction uses a clique for the selected A-row vertices and connects them to y_j vertices according to B; y_j lies in the giant component exactly when AB[i, j] = 1.Source: §4.1 · p. 13

4.2 Recognizing AT-free Graphs in Matrix Multiplication Time

  • For every x with non-empty H_x, at least |V_x|²/(4s_x) − |V_x| pairs (y,C) in V_x × H_x satisfy C ∈ H_y, where s_x is the largest component size in H_x.Source: §4.2 · pp. 14–15
  • For AT-free graphs, the total number of distinct neighborhood-deleted components across all G_x is at most 400 n log n.The proof partitions components by size and occurrence counts, then bounds each class using a bipartite graph.Source: §4.2 · p. 15
  • A deterministic O~(n^ω)-time algorithm recognizes whether a graph is AT-free.It counts distinct neighborhood-deleted components and, when their number is at most 400 n log n, reduces recognition to triangle detection on a graph with O(n log n) vertices.Source: §4.2 · p. 16
  • G is AT-free if and only if the constructed graph T is triangle-free, and the recognition algorithm runs in Õ(n^ω) time.A triangle in T yields an asteroidal triple among its representatives; the converse proof shows an asteroidal triple can be replaced by representatives to obtain a triangle in T.Source: §4.2 · p. 17

4.3 Listing Dominating Pairs in Matrix Multiplication Time

  • A deterministic Õ(n^ω)-time algorithm lists all dominating pairs.It marks non-dominating pairs using witnesses from neighborhood-deleted components, then returns the unmarked pairs.Source: §4.3 · pp. 17–18

4.4 Listing Two-Pairs in Matrix Multiplication Time

  • A deterministic Õ(n^ω)-time algorithm lists all two-pairs, characterized by N(u) ∩ N(v) = N(C_v(u)) for non-neighboring u, v.The algorithm tests representatives among the vertices in each neighborhood-deleted component that maximize their common-neighbor count with v.Source: §4.4 · pp. 19–20

4.5 Recognizing Quasi-Triangulated Graphs Faster

  • O(n^2.5275) is the dense-graph running time for the decremental simplicial-vertex algorithm, whose general bound is min over Δ in [1..n] of {n/Δ · MM(n, Δ, n) + m·Δ}.It maintains each vertex’s count of missing edges in its neighborhood; within each phase, updates take O(Δ) time.Source: §4.5 · pp. 21–22
  • Across all vertex removals, the total intra-phase update time is O(m·Δ).Each removed vertex requires O(Δ) time per neighbor, and the sum of removed-vertex degrees is at most 2m.Source: §4.5 · p. 22

4.6 Lower Bound for Finding 𝑢𝑣-trails

  • For an n-node graph G, in O(n^2) time one can build a (3n+4)-node graph H with designated vertices u and v such that H has a uv-trail iff G has a triangle.Source: §4.6 · p. 22
  • For every k ≥ 3, an O(T)-time algorithm detecting a uv-trail at distance k yields an O(T)-time triangle-detection algorithm.For k > 3, the reduction extends the construction with a path of length k−3 to a new endpoint.Source: §4.6 · pp. 23–24

A Motivation for the Kratsch-Spinrad problems

The paper situates the studied structures within four graph classes linked by structural characterizations and algorithmic properties. Their defining obstructions and special vertex pairs support ways to understand and decompose these classes.

Perfect graphs

  • Perfect graphs have every induced subgraph’s chromatic number equal to its maximum-clique size; star-cutsets are structural obstructions used to decompose graph classes and prove perfection [Chv85, Ree87].The Strong Perfect Graph Theorem was conjectured by Berge [Ber60, Ber61] and proved by Chudnovsky, Robertson, Seymour, and Thomas [CRST06].Source: A Motivation for the Kratsch-Spinrad… · p. 29

Triangulated graphs

  • Triangulated (chordal) graphs forbid induced cycles of length four or more, and their clique-cutset characterization explains how separating cliques enable decomposition into independently solvable pieces [Dir61, Gav72, RTL76].Dirac’s equivalent characterization also says each induced subgraph is a clique or contains two non-adjacent simplicial vertices [Dir61].Source: A Motivation for the Kratsch-Spinrad… · p. 29

Weakly triangulated graphs

  • Weakly triangulated graphs contain no induced holes or antiholes, and two-pairs play a role analogous to simplicial vertices in their structural characterization [Hay85, CR93].Every induced subgraph is either complete or contains a two-pair [CR93] (see also [ES95, CRS02]); two-pairs also inform efficient algorithms [HHM90, HSS07].Source: A Motivation for the Kratsch-Spinrad… · p. 29

AT-free graphs

  • AT-free graphs generalize a property of interval graphs: every such graph contains a dominating pair realizing the diameter [COS97].Interval graphs are exactly graphs that are both chordal and AT-free [LB62]; AT-free structure also supports polynomial-time algorithms for several NP-hard problems [Sta12, KM12, BKKM99, Kra00, KMT08].Source: A Motivation for the Kratsch-Spinrad… · p. 29

B Dominated vertex is equivalent to OV

The section establishes quadratic-time reductions linking Dominated Vertex, Orthogonal Vectors (OV), and a quantified neighborhood condition. Its constructions encode orthogonality through graph domination and use adjacency matrices for the reverse direction.

Dominated Vertex to OV

  • A graph’s adjacency matrix, complement, and identity matrix yield an OV instance on two n-vector sets in 2n dimensions that detects a dominated vertex.The zero-product condition captures the neighborhood adjacency requirement and excludes the diagonal case.Source: B Dominated vertex is equivalent to OV · pp. 29–30

Single-set OV

  • The standard two-set-to-single-set OV reduction still applies by combining the vectors with two added columns that distinguish the two sets.Rows representing X receive 01 in those columns, while rows representing columns of Y receive 10.Source: B Dominated vertex is equivalent to OV · p. 30

OV to Dominated Vertex

  • An O(n^2)-time construction maps two n-vector sets to an O(n)-node graph with a dominated vertex exactly when an orthogonal vector pair exists.The construction uses vertex sets X, Y, X′, Y′, X″, C′, and C″; coordinate incidences encode vector bits so an orthogonal pair corresponds to domination from X to Y.Source: B Dominated vertex is equivalent to OV · p. 30
  • Copies, cliques, and matchings rule out unintended dominating pairs, leaving only vertices in X potentially dominated by vertices in Y.The construction’s remaining domination condition is equivalent to orthogonality of the corresponding vectors.Source: B Dominated vertex is equivalent to OV · pp. 30–32

Equivalence theorem

  • Dominated Vertex in Θ(n)-node graphs, OV on Θ(n) vectors in Θ(n) dimensions, and the quantified neighborhood problem are equivalent under O(n^2)-time reductions.The neighborhood condition asks whether some neighbor y of x is adjacent to every neighbor z of x.Source: B Dominated vertex is equivalent to OV · p. 32
Loading 2610.22133v1…