The monotonicity conjecture for recognizing generating complete bipartite subgraphs

From papers

Let $p,q$ be positive integers with $p\geq 1$ and $q\geq 2$ , and let $i\leq p$ and $j\leq q$ . Let $\Psi$ be a family of graphs for which recognizing generating subgraphs isomorphic to $K_{i,j}$ is NP-complete. Monotonicity conjecture. Then recognizing generating subgraphs of graphs in $\Psi$ isomorphic to $K_{p,q}$ is NP-complete as well. This conjecture proposes that NP-completeness for recognizing generating subgraphs isomorphic to a smaller complete bipartite graph extends to larger complete bipartite graphs within the same family. The paper establishes the corresponding complexity results for the relevant complete bipartite graphs by minor modifications of an earlier proof, but the stated general implication is presented as a conjecture.

Progress summary

Open

The conjecture remains unproved in general, although the predicted hardness is known for several specific graph families.

The monotonicity conjecture asserts that, for a graph family $\Psi$ , NP-completeness for recognizing generating copies of $K_{i,j}$ should imply NP-completeness for $K_{p,q}$ whenever $i\leq p$ and $j\leq q$ . It is stated as Conjecture 24 in Recognizing generating subgraphs revisited.

Known results

For graphs without cycles of lengths $3$ and $5$ , recognizing generating $K_{1,2}$ is NP-complete.
In that same family, minor modifications yield NP-completeness for every $K_{p,q}$ with $p\geq 1$ and $q\geq 2$ .
For bipartite graphs of girth at least $6$ , the corresponding hardness results are also recorded.

Current status (as of August 2026): The general monotonicity conjecture remains open; only particular-family cases are established, with no publicly verified proof or counterexample found.

Sources

ar5iv.labs.arxiv.org

Sources & referencesView supporting material

Primary source

Vadim E. Levit and David Tankus, “Recognizing generating subgraphs revisited”, arXiv:1811.04433 (2018).

1 week ago

Counterexample to the literal arbitrary-family statement

Let $\Psi$ be the family of graphs containing no cycles of length $4$ or $5$ , where the forbidden cycles need not be induced.

Take

(i,j)=(1,1), \qquad (p,q)=(2,2).

A generating $K_{1,1}$ is exactly a relating edge. Levit and Tankus proved in Theorem 2.1 of On Relating Edges in Graphs without Cycles of Length 4 that deciding whether a specified edge is relating is NP-complete for graphs in $\Psi$ . Thus the conjecture's premise holds for $(i,j)=(1,1)$ .

However, no graph in $\Psi$ contains a $K_{2,2}$ . Indeed, if its two sides are $\{x_1,x_2\}$ and $\{y_1,y_2\}$ , then its four cross-edges form the cycle

x_1y_1x_2y_2x_1,

which is a cycle of length $4$ .

Consequently, no graph in $\Psi$ contains a generating $K_{2,2}$ , so the corresponding recognition language has no yes-instances. The empty language is not NP-hard under polynomial-time many-one reductions: for example, a satisfiable SAT instance would have to map to a yes-instance, but none exists. Hence this recognition problem is not NP- complete.

The premise therefore holds at $(1,1)$ while the conclusion fails at $(2,2)$ , disproving Conjecture 24 as stated.

This does not affect the paper's preceding result for its particular family of graphs without cycles of lengths $3$ and $5$ . It only refutes the subsequent extrapolation to an arbitrary graph family; a repaired statement would need an appropriate closure or padding hypothesis on $\Psi$ .

Conjecture source: https://arxiv.org/abs/1811.04433

Hardness theorem: https://arxiv.org/abs/0908.4016

0 endorsements

Samuel Schlesinger · 4 days ago