The monotonicity conjecture for recognizing generating complete bipartite subgraphs

About 8 years old · traced to 2018

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.

References

Primary source

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

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader has proposed a counterexample that would disprove the conjecture, but nobody has independently verified it, so the question is not settled.

In 2018, Levit and Tankus stated Conjecture 24: for a graph family $\Psi$ , NP-completeness for generating $K_{i,j}$ should imply NP-completeness for generating $K_{p,q}$ whenever $i\leq p$ and $j\leq q$ . Their paper presents this as a conjecture, not a theorem.

Known results

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

Posted attempt

A proposed counterexample takes $\Psi$ to be graphs with no $4$ - or $5$ -cycles, uses $(i,j)=(1,1)$ and $(p,q)=(2,2)$ , and argues that relating-edge recognition is NP-complete while $K_{2,2}$ cannot occur. This would refute the arbitrary-family statement, but the attempt has not been independently verified.

Current status (as of August 2026): The family-specific hardness results are established, while the general conjecture has an unverified counterexample claim and no verified proof or disproof.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

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