Papers for

complex networks analysts

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Clique transversal size problem proved hard for complex graphs

W[1]-Hardness of Upper Clique Transversal

Abstract: A clique transversal of a graph is a set of vertices intersecting every maximal clique. We prove that deciding whether a graph has an inclusion-wise minimal clique transversal of size at least $k$ is W[1]-hard when parameterized by $k$.

Sun 4 OctComputational ComplexityDiscrete MathematicsData Structures and Algorithms

The gist

This paper looks at a puzzle about graphs, which are like networks of dots and lines. The puzzle is about finding a special group of dots that touches every big tightly connected group called cliques. The authors show that figuring out if such a group can be big is very hard in a technical sense, meaning no fast shortcuts are likely to exist. This helps us understand the limits of solving these kinds of network problems.

Open → 2610.04917v1