  Answer Set Programming (ASP) is a problem modeling and solving framework for
several problems in KR with growing industrial applications. Also for studies
of computational complexity and deeper insights into the hardness and its
sources, ASP has been attracting researchers for many years. These studies
resulted in fruitful characterizations in terms of complexity classes,
fine-grained insights in form of dichotomy-style results, as well as detailed
parameterized complexity landscapes. Recently, this lead to a novel result
establishing that for the measure treewidth, which captures structural density
of a program, the evaluation of the well-known class of normal programs is
expected to be slightly harder than deciding satisfiability (SAT). However, it
is unclear how to utilize this structural power of ASP. This paper deals with a
novel reduction from SAT to normal ASP that goes beyond well-known encodings:
We explicitly utilize the structural power of ASP, whereby we sublinearly
decrease the treewidth, which probably cannot be significantly improved. Then,
compared to existing results, this characterizes hardness in a fine-grained way
by establishing the required functional dependency of the dependency graph's
cycle length (SCC size) on the treewidth.
