We are delighted to share our two new publications that have been published in the journal Discrete Applied Mathematics. The first author of both papers is József Pintér, our laboratory's Deputy Head of Research and Technology. Each paper settles an open question in computational complexity, and in both cases the answer turned out to be the opposite of what was expected.

Conformability is NP-complete. A total coloring colors the vertices and edges of a graph together so that any two elements that touch receive different colors. In 1988, Chetwynd and Hilton introduced conformability as a way to study this hard problem. A graph is conformable if it has a proper coloring with Δ+1 colors (where Δ is the maximum degree) whose color classes satisfy a parity condition. Every graph that admits a total coloring with Δ+1 colors is conformable, so conformability is a necessary condition for an optimal total coloring. Whether this condition can be checked efficiently was an open question, and the evidence pointed toward efficient solvability.

József proves the opposite: deciding conformability is NP-complete. The hardness holds even when the graph is connected, regular, of odd order, has independence number three, and has degree at least half the number of vertices. The proof starts from the perfect triangle packing problem and builds on a new regularization lemma, which makes a K₄-free graph regular without creating or destroying a single triangle. This tool may prove useful beyond this paper. The result settles the general complexity question and shows that regularity alone does not determine where a graph class falls: for sparse and bipartite regular graphs the problem is efficiently solvable, whereas for dense regular graphs with small independence number it is hard.

Few caches, fast answers. When millions of people watch the same show, services such as Netflix store popular content in caches close to the viewers. Deciding what to store where, when cache capacity is limited and each user can reach only a few caches, is known as the network caching problem. In general, the problem is NP-hard. At AAAI 2025, Ganian, Mc Inerney, and Tsigkari began studying its parameterized complexity. For the homogeneous variant, which assumes content items of equal size, they identified six parameterizations whose status they could not determine. They showed that these six cases stand or fall together, and conjectured that all of them are W[1]-hard.

In a paper co-authored with Regina Stangl, József settles the entire family in the opposite direction. The authors prove that the problem is fixed-parameter tractable when parameterized by the number of caches: for a fixed number of caches, the running time is polynomial in the input size, and all six open cases follow from this. The key observation is a hidden block structure. With C caches, each content item has only 2^C possible placement patterns, and different items interact with each other only through the capacity constraints of the C caches. This is exactly the shape of an n-fold integer program, for which fast algorithms are known. Beyond resolving the conjecture, the formulation offers a compact, exact model for instances with few caches.

Congratulations to József and Regina on these publications!

NP-completeness of conformability: https://www.sciencedirect.com/science/article/pii/S0166218X26005457?via%3Dihub

Network caching parameterized by the number of caches: https://www.sciencedirect.com/science/article/pii/S0166218X26005548?via%3Dihub