Alex Meiburg / Timeroot

Quantum ⊕ Physics ⊗ Algorithms

Graph Parameters

See also the substructure page

These are different numerical graph parameters that can be computed. They range from very simple (vertex count) to difficult (Shannon capacity). Some are integer, some are real valued.

I try to give the complexity of computing them: P or NPC, mostly. I also try to give their parameterized complexity and their complexity of approximation. When the complexity is already P, I mark the other two complexity columns with - to show that it’s pretty irrelevant1.

“Monotonic” means “how does this change when you add edges?”. ⬆️ means it’s weakly increasing with edge additions, ⬇️ means it weakly decreasing with edges, and ❌ means that it isn’t monotonic.

The “relationship” column is purely subjective: it’s the one relationship (to other parameters) that I view as most important in summarizing their relationship to each other. There’s certainly room to build this out. If the row says something like i | c | p | a | m | r, that’s just placeholder for me to fill in later.

Name Notation Integer? Complexity Parameterized Approximation Monotonic Relationship
Sizes              
Order V(G) Y P - - =  
Size E(G) Y P - - ⬆️ E ≤ V*(V-1)/2
Max Degree Δ(G) Y P - - ⬆️  
Min Degree δ(G) Y P - - ⬆️  
Radius r(G) Y P - - ⬆️  
Diameter d(G) Y P - - ⬆️  
Girth g(G) Y P - - ⬇️  
Constraint-Based              
Clique No. ω(G) Y NPC W[1]C a ⬆️ ceil(V^2/(V^2 - 2*E)) ≤ ω2
Chromatic No. χ(G) Y NPC paraNPC3 … ⬆️ ω ≤ χ
Chromatic Index χ’(G) Y NPC     ⬆️ Δ ≤ χ’ ≤ Δ+1
Independence No. α(G) Y NPC p a ⬇️ α(G) = ω(G̅)
Domination No. γ(G) Y NPC W[2]C LogAPXC ⬆️ γ ≤ α
Independent domination No. i(G) Y c p a r γ ≤ i ≤ α
Intersection No. ? Y NPC FPT NPC?4 ? …
Minimum Vertex Cover VC(G) Y c p a m r
Connectivity              
Crossing No. cr(G) Y c p a m r
Hadwiger No. h(G) Y NPC FPT   ⬆️ Does χ(G) ≤ h(G)?
Conductance5 ϕ(G)5 N P - - ⬆️ r
Genus gn(G)6 Y NPC FPT   ⬆️  
Edge-connectivity ec(G)7 Y P - - ⬆️ r
Vertex-connectivity vcn(G)7 Y P - - ⬆️ r
Circumference cfr(G)7 Y NPC p a ⬆️ r
Matrix Ranks              
Verdière’s invariant μ(G) i c p a m r
Minimum rank mr(G) i c p a m r
Independence-like              
Lovasz No. ϑ(G) N P - - ? ω(G) <= ϑ(G̅) <= χ(G)
Shannon Capacity ϴ(G) N ?8 - - ⬇️ α <= ϴ <= ϑ
Entanglement-assisted Shannon capacity ϴ*(G) i c p a m r
Entanglement-assisted One-Shot Zero-Error capacity c0*(G) i c p a m r
“Beta Parameter”9 β(G) N P? - - ⬇️ α <= β <= ϑ
Chromatic-like              
Orthogonal rank ξ(G) i c p a m r
Normalized orthogonal rank ξ’(G) i c p a m r
Projective rank ξf(G) i c p a m r
Circular Chromatic No. χc(G) i c p a m r
Fractional Chromatic No. χf(G) i c p a m r
Vector Chromatic No. χv(G) i c p a m r
Vectorial Chromatic No. χvect(G) i c p a m r
Quantum Chromatic No. χq(G) i c p a m r
Rank-1 Quantum Chromatic No. χ(1)q(G) i c p a m r
Other?              
Hajós No. h(G) Y ?10 - - ? h <= 2^(V^2/3 - E + 1)10

Parameters and binary operations

This table describes how parameters change under operations. V and E are omitted, as those are already discussed above.

Parameter →
↓ Op		 ω χ α γ i ϑ ϴ β
Cartesian Prod ? = Max some bounds ≥ Prod? ? ? ? ?
Tensor Prod ? ≤ Min11 ? ? ? ? ? ?
Strong Prod = Prod ? ? ? ? ? ? ?
Conormal Prod ? ? ? ? ? ? ? ?
Modular Prod ? ? ? ? ? ? ? = Prod
Lexico. Prod ? ? ? ? ? ? ? ≥ Prod
Homomorphic Prod ? ? ? ? ? ? ? ?
Disjoint Union = Max = Max = Sum = Sum ? ? ? ?
Graph Join = Sum = Sum = Max ≤ 212 ? ? ? ?
Unary                
Mycielskian Max(2,ω) χ+1 a formula γ+1 ? ? ? ?

Footnotes

I have a todo list for this page.

  1. It would be an interesting question to see if there are parameters in P that can be efficiently approximated much faster. Spectral radius is an obvious candidate, as current SOTA algorithms compute it in O(n^2.38), which might be slow for some people’s tastes. Something like “average pairwise distance” can be computed in O(n^3) time but maybe approximated better. The Lovasz number can be efficiently computed with an SDP but that’s moderately slow. Have at it, ye lovers of the fine-grained! ↩

  2. This is an equivalent way of writing Turán’s theorem. ↩

  3. ParaNPC means that deciding a fixed parameter (e.g. k=3 – is the graph 3-colorable?) is already NP-Complete, this gives the parameterized class para-NP-complete, or paraNPC. ↩

  4. If I write that something is “NPC” to approximate, this means that I’ve come across a statement that it’s “NP-hard to approximate” and haven’t investigated as to how hard to approximate. ↩

  5. Conductance is also often called the Cheeger constant, which is more typical for unweighted graphs. In those contexts, it is written h(G). We use the conductance notation of ϕ(G) to avoid conflict with the Hadwiger number. ↩ ↩2

  6. Graph genus is often notated as γ(G). We write gn(G) to avoid conflict with the domination number γ(G) and girth g(G). ↩

  7. This is nonstandard notation that I’ve invented here, because it doesn’t seem to have a standard number in the literature (except perhaps a generic k). ↩ ↩2 ↩3

  8. It is unknown whether the Shannon capacity is even decidable. ↩

  9. I’d personally propose naming this the “quantum independence radius”. The authors simply call it the “beta parameter”. ↩

  10. Proving that h <= poly(V) would imply that NP=coNP, see the discussion here. Little is know about how hard h is to compute, except that (trivially) it’s in NEXP because of the exponential bounds on its size. ↩ ↩2

  11. It was believed that the chromatic number of tensor product was exatly the minimum of the chromatic number of the factors, known as Hedetniemi’s_conjecture. It is easy to see that it is at most the minimum of the factors. In 2019 the conjecture was disproved, that the < Min case can occur too. ↩

  12. The domination number of a graph join is always exactly two (by taking one vertex from each half of the join), unless either factor has a universal vertex (i.e. has a domination number of one), in which case the domination number is one; unless both addends are the empty graph, in which case the domination number is zero. ↩