Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.16327 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910141909041152 |
|---|---|
| author | Standish, Russell K. |
| author_facet | Standish, Russell K. |
| contents | In \cite{Standish25c}, I explored the connection between star
complexity and information based complexity. Because of the
numerical difficulty in computing star complexity, I introduced a
proxy measure that is an upper bound to star complexity, and showed
a strong albeit non-linear relationship between the measures.
In this paper, I introduce a tighter upper bound, by exploiting the
well-known ABC package used to optimise logic circuits. In testing
the new measure, I found that I had been computing the {\em formula
complexity} variant of star complexity, rather than the tighter
{\em circuit complexity} variant. Since Jukna clearly states the
connection between star complexity and circuit complexity, I have
modified the graph walking algorithm to capture circuit complexity
rather than formula complexity.
With this new ABC-based measure, applied to a set of 1000 500 vertex
Erdös-Renyi graphs, a more linear relationship between star
complexity and information based complexity is found. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16327 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An improved upper bound measure of star complexity of graphs Standish, Russell K. Computational Complexity 94A17, 05C30 G.2.2 In \cite{Standish25c}, I explored the connection between star complexity and information based complexity. Because of the numerical difficulty in computing star complexity, I introduced a proxy measure that is an upper bound to star complexity, and showed a strong albeit non-linear relationship between the measures. In this paper, I introduce a tighter upper bound, by exploiting the well-known ABC package used to optimise logic circuits. In testing the new measure, I found that I had been computing the {\em formula complexity} variant of star complexity, rather than the tighter {\em circuit complexity} variant. Since Jukna clearly states the connection between star complexity and circuit complexity, I have modified the graph walking algorithm to capture circuit complexity rather than formula complexity. With this new ABC-based measure, applied to a set of 1000 500 vertex Erdös-Renyi graphs, a more linear relationship between star complexity and information based complexity is found. |
| title | An improved upper bound measure of star complexity of graphs |
| topic | Computational Complexity 94A17, 05C30 G.2.2 |
| url | https://arxiv.org/abs/2604.16327 |