Algorithms for Short Human-Verifiable Proofs of Non-Word-Representability
Source: arxiv.org/abs/2611.08553
A graph is word-representable if it can be represented using alternation of letters in words. The class of word-representable graphs generalizes several important graph families and admits a characterization via semi-transitive orientations. Recognizing word-representability is an NP-complete problem, and a major bottleneck in the theory of word-representable graphs is providing efficient justifications of non-word-representability of graphs, rather than merely referring to software verification. Recently, Kitaev and Sun initiated the development of methods for the automatic generation of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.08553
curl -X POST /api/v1/records/arxiv/2611.08553/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.08553/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'