Finding non-bisimplicial and triad-free minimal separators

1. Introduction

• A polynomial-time algorithm decides whether every minimal separator in a graph is the union of at most two cliques.The class G2 consists of graphs whose minimal separators are unions of at most two cliques.Source: §1 · p. 2
• For K2,3-induced-minor-free graphs, the algorithm finds a shortest odd minimal separator if one exists, supporting recognition of graphs in G2.The proof outline first tests whether every minimal separator is triad-free, which is equivalent to K2,3-induced-minor-freeness.Source: §1 · p. 2
• The recognition algorithm detects a shortest odd minimal separator by finding connected sets on opposite sides whose neighborhoods contain a common odd antihole.Structural lemmas make it possible to find the sets by guessing a bounded number of vertices, even when the separator and antihole are large.Source: §1 · p. 2
• A polynomial-time algorithm either finds a triad-free u-v separator or determines that none exists.Triad-free means the separator has independence number at most two.Source: §1 · p. 2
• The triad-free separator algorithm reduces its remaining task to the polynomial-time list 2-clique cutset problem.Its structural step identifies, among polynomially many candidates, a subset whose removal leaves a bisimplicial remainder.Source: §1 · p. 3
• The list triad-free cutset problem admits a polynomial-time algorithm, with allowed vertex lists specifying the two sides and the cutset.A solution requires anticomplete sides and a triad-free cutset.Source: §1 · p. 3
• The connected list triad-free cutset problem is polynomial-time solvable, but the minimal version is NP-hard even for complements of bipartite graphs.The minimal version requires each cutset vertex to have a neighbor on both sides.Source: §1 · p. 3

1.1. Outline of the paper.

• The paper develops structural properties of shortest odd minimal separators before using them in the recognition algorithm, then treats prescribed-vertex separators and list-constrained cutsets.The latter results include the polynomial-time connected-list case and hardness of the minimal-list case.Source: §1 · p. 3, §1.1 · p. 4

2. Definitions

• N(S) contains vertices outside S with at least one neighbor in S, while N[S] adds S itself.M(S) is the set of vertices outside N[S].Source: §2 · p. 4
• A vertex outside S is small for S if it has at most two non-neighbors in S, and big for S if it has at least three.B(S) denotes the vertices outside S that are big for S.Source: §2 · p. 4
• A stretch of a vertex on an antihole is an antipath of at least two vertices whose ends are nonadjacent to the vertex and whose interior is complete to it.A stretch is long when it has at least five vertices.Source: §2 · p. 4

3. The structure of G′

• Every vertex big for A has an even stretch in A.The stretches partition the antihole with overlap at non-neighbors; because A is odd, at least one stretch is even.Source: §3 · p. 4
• Every vertex of S is small for A.If a separator vertex were big, an even stretch would produce a shorter odd antihole within S.Source: §3 · pp. 4–5
• An S-full component contains a connected subset full to A with at most six vertices small for A.The proof treats the cases where the smallest such connected subset is a path or is not a path.Source: §3 · p. 5
• When A is known, enumerating sets of at most six small vertices and taking components with B(A) can find a component full to A inside an S-full component.The search also supports finding a shortest odd antihole or a subset of A of size at most 22 that preserves the relevant big vertices.Source: §3 · p. 5
• If a big vertex has a long stretch in A, each of its other stretches has exactly three vertices.The argument rules out two consecutive non-neighbors and uses a shortest even stretch to constrain the other stretches.Source: §3 · p. 5
• For any B ⊆ B(A), either two vertices in B cover A by their neighborhoods, or a subset A′ of at most 22 vertices preserves every vertex of B as big.The bounded subset is formed around the ends of a longest stretch.Source: §3 · pp. 5–6

4. Finding a non-bisimplicial minimal separator

• A polynomial-time algorithm decides whether every minimal separator in G is the union of at most two cliques.The proof outline uses polynomial-time detection of a K2,3 induced minor as an initial test.Source: §4 · p. 6
• The algorithm enumerates subsets of at most 22 vertices and sets of at most six vertices, then tests components and common neighborhoods for odd antiholes.It also checks common neighborhoods of vertex pairs from two components, adding shortest odd antiholes found there to its candidates.Source: §4 · p. 6
• The correctness argument shows that for a K2,3-induced-minor-free graph outside the class, the search detects an odd minimal separator.A shortest odd minimal separator and two of its full components provide the structure used to establish that a candidate is found.Source: §4 · pp. 6–7
• If G is K2,3-induced-minor-free but has a non-bisimplicial minimal separator, it has an odd minimal separator.The complement of that separator is non-bipartite and, since it is triangle-free, contains an odd hole.Source: §4 · p. 7

5. Finding a triad-free separator

• For a minimal separator S with α(S) = 2, each S-full component contains a component of G[M(e) ∪ {x}] that meets every non-edge of S through its neighborhood.The construction chooses a maximal component C(e, x) and uses the connectivity and fullness of the S-full component.Source: §5 · pp. 7–8
• If X1 and X2 each have a neighbor in at least one endpoint of every non-edge of S, then removing N(X1) ∩ N(X2) from S leaves a bisimplicial set.The remaining vertices can be partitioned into two cliques.Source: §5 · p. 8
• The auxiliary graph and allowed-vertex lists let the two cliques returned by the cutset algorithm combine with S while preserving triad-freeness.The proof uses the gadget vertices to rule out a triad among the combined sets.Source: §5 · pp. 8–9
• A polynomial-time algorithm either finds a triad-free u-v separator or determines that none exists.The algorithm checks each returned candidate for both separation and triad-freeness.Source: §5 · pp. 8–9
• The algorithm enumerates components built from non-edges and vertices, forms S = N(C1) ∩ N(C2), and encodes the remaining task as a list 2-clique cutset instance.It adds gadget vertices for edges whose endpoints would form a triad with S, then checks the resulting separator candidate.Source: §5 · p. 8
• The candidate-component family has at most O(|V(G)|^3) members, and constructing and solving each list cutset instance takes polynomial time.Checking that a candidate is a triad-free u-v separator is also polynomial-time.Source: §5 · p. 9

• The list triad-free cutset problem and its connected variant each admit a polynomial-time algorithm.Source: §6 · pp. 9–10
• The list triad-free cutset problem reduces to finding a triad-free u-v separator in an augmented graph, with solutions mapped back to the original instance.The construction adds auxiliary vertices and uses Theorem 1.4 to find a separator or report none exists.Source: §6 · pp. 9–10
• For connected list triad-free cutsets, the algorithm first tests the list 2-clique cutset problem, then tries instances excluding each induced path a-b-c in S.A non-clique connected solution contains such a path, and solutions to the modified instances remain connected because they are triad-free.Source: §6 · p. 10
• Minimal list triad-free cutset is NP-hard, even when the input graph is the complement of a bipartite graph.The reduction is from extension minimal bipartite vertex cover, which is NP-hard.Source: §6 · p. 11

• Theorem 1.4’s algorithm was developed in a conversation with GPT-6 Astra; the authors wrote the paper.Source: §8 · p. 11