# Inferring Attack Relations for Gradual Semantics

Nir Oren
University of Aberdeen
Scotland
<EMAIL_ADDRESS>
&Bruno Yun
University of Aberdeen
Scotland
<EMAIL_ADDRESS>

###### Abstract

A gradual semantics takes a weighted argumentation framework as input and
outputs a final acceptability degree for each argument, with different
semantics performing the computation in different manners. In this work, we
consider the problem of attack inference. That is, given a gradual semantics,
a set of arguments with associated initial weights, and the final desirable
acceptability degrees associated with each argument, we seek to determine
whether there is a set of attacks on those arguments such that we can obtain
these acceptability degrees. The main contribution of our work is to
demonstrate that the associated decision problem, i.e., whether a set of
attacks can exist which allows the final acceptability degrees to occur for
given initial weights, is NP-complete for the weighted h-categoriser and
cardinality-based semantics, and is polynomial for the weighted max-based
semantics, even for the complete version of the problem (where all initial
weights and final acceptability degrees are known). We then briefly discuss
how this decision problem can be modified to find the attacks themselves and
conclude by examining the partial problem where not all initial weights or
final acceptability degrees may be known.

_K_ eywords Gradual Semantics $\cdot$ Argumentation $\cdot$ Complexity

##  1 Introduction

Abstract argumentation semantics associate a justification status with a set
of arguments based on interactions between arguments. Such interactions can
include inter-argument attacks [1], or preference-based defeats [2, 3, 4, 5,
6], or may consider both of these together with some supportive relationship
[7, 8, 9, 10]. Given such a framework, an argument may be considered justified
if it appears in one (resp. many or all) _extensions_ , where such extensions
– sets of non-conflicting arguments accepted together – are computed according
to the argumentation semantics, or based on the label assigned to the argument
(we refer the reader to [11] for an introduction to the most common
argumentation semantics).

Arguments often have associated weights, and different semantics have been
proposed which consider the weight associated with an argument [12, 8, 10,
13]. While some semantics developed in this context return whether an argument
is, or is not justified [12], many other _ranking-based_ semantics either
return a preference ordering over arguments by making use of the argument’s
initial weight or associate a numeric _final acceptability degree_ with each
argument in the framework. Such ranking-based semantics have been used to —
for example — identify irrationality in reasoning [14] by examining whether
the initial weights associated with an argument affect the argument’s final
acceptability degree in an appropriate manner (i.e., consistent with the
ranking-based semantics being used); refining the results obtained by
extension semantics [15, 16]; and applied to multi-agent settings [17].

The top portion of Fig. 1 shows the reasoning process used when reasoning
using gradual semantics. Here, a weighted argumentation framework consisting
of arguments, attacks and initial weights associated with arguments is
provided as input. A gradual semantics is then used to compute a _final
acceptability degree_ for each argument. In many semantics, these final
acceptability degrees are then used to compute a preference ordering over the
arguments.

More recent work has considered different combinations of inputs and outputs
to the problem. For example, [13] seeks to identify a set of initial weights
for arguments based on the final argument preference ordering and
argumentation semantics, while [18] determines the preferences between
arguments given argument justification status, semantics and argumentation
framework. In this paper, and as illustrated in the bottom portion of Fig. 1,
we consider the problems of determining whether a set of attacks between
arguments can be identified given specific argumentation semantics, the final
acceptability degrees, and the initial weights. As discussed further in
Section 5, we leave the problem of using preferences over arguments as input
for our problem as future work. While it is true that the problem we consider
is somewhat abstract and has limited real-world applications, it serves as a
departure point for potentially important applications of argumentation to
opponent modelling [19, 20] and preference elicitation [18].

Figure 1: The process (top) by which a gradual semantics is applied to compute
an acceptability preference between arguments and (bottom) the inverse problem
considered in this paper. The “final acceptability degrees" are now used as
input. That is, given arguments, initial weights, and desirable final
acceptability degrees, can we find a suitable set of attacks?

While other ranking-based semantics are described in the literature, we
consider three popular gradual semantics (the weighted h-categoriser, the
weighted card-based, and the weighted max-based semantics [21]). These three
semantics were chosen due to their similarity to one another, and due to the
way in which a similar approach can be used to solve the problem under
consideration when these semantics are used. We show that when given all final
acceptability degrees and initial weights, the problems for weighted
h-categoriser and weighted card-based semantics are both NP-complete, while
the problem can be solved in polynomial time for the weighted max-based
semantics.

The remainder of this paper is structured as follows. In Section 2, we provide
the necessary background to understand the remainder of the paper, introducing
the h-categoriser semantics. Section 3 formalises the decision problem of
whether attacks can be found for gradual semantics and then demonstrates that
it is NP-complete for some semantics. In Section 4 we discuss solvers for our
problem, and consider related and future work (including a partial version of
the problem) in Section 5.

##  2 Background

As discussed above, we situate our work in the context of _weighted_ abstract
argumentation frameworks (WAFs), which can be encoded as graphs with weighted
nodes. Each argument has an initial weight (also called “basic score” in [22])
from $[0,1]$. The smaller the initial weight of an argument, the weaker the
argument. The initial weight of an argument may represent different issues
like the likelihood degree of its premises [23], the degree of trust in its
source [24], or an aggregation of votes provided by users [25] among others.
In this paper, the origin of the weights and arguments is left unspecified.
Similarly, arguments and attacks are considered abstract notions.

######  Definition 1.

A _weighted argumentation framework_ is a triple
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ where $\mathcal{A}$ is a
_finite_ set of arguments, $\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$
is a binary attack relation, and $w:\mathcal{A}\to[0,1]$ is a total weighting
function which associates an _initial weight_ between $0$ and $1$ to each
argument.

Given an argument $a\in\mathcal{A}$, we refer to $w(a)$ as $a$’s _initial
weight_. For any argument $a\in\mathcal{A}$, the set
$\\{b\in\mathcal{A}|(b,a)\in\mathcal{D}\\}$, denoted by $\mathtt{Att}(a)$,
contains all attackers of $a$. Similarly, we define
$\mathtt{Att}^{*}(a)=\\{b\in\mathcal{A}|(b,a)\in\mathcal{D}$ and $w(b)>0\\}$,
i.e., the set of attackers of $a$ with strictly positive weights. When the
current argumentation framework $\mathcal{F}$ is not clear from the context,
we will use the notation $\mathtt{Att}_{\mathcal{F}}$ and
$\mathtt{Att}^{*}_{\mathcal{F}}$ respectively.

A gradual semantics $\sigma$ takes as input a weighted argumentation framework
and outputs a function that associates a _final acceptability degree_ for each
argument111Often, the final step in using a gradual semantics involves using
this final acceptability degree to compute a preference ordering over
arguments.. Several such semantics have been described in the literature. In
this paper, we focus on three widely used gradual semantics introduced by
Amgoud et al., i.e. the weighted h-categoriser, the weighted max-based, and
the weighted card-based semantics, denoted $\sigma_{HC}$, $\sigma_{MB}$ and
$\sigma_{CB}$ respectively [21].

The weighted h-categoriser considers the initial weight of the argument as
well as the sum of the acceptability degrees of all its attackers to determine
the acceptability degree of the argument. In this semantics, all (non-zero)
attackers will be considered when determining the acceptability degree of an
argument and the number of attackers is not used.

######  Definition 2.

The weighted h-categoriser semantics, denoted $\sigma_{HC}$, is the function
that takes as input any weighted argumentation framework
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ and returns the function
$\sigma^{\mathcal{F}}_{HC}:A\to[0,1]$ such that for all
$a\in\mathcal{A},\sigma^{\mathcal{F}}_{HC}(a)=HC_{\infty}(a)$, where:

$HC_{i}(a)=\begin{cases}w(a)&\text{if }i=0\\\
\frac{w(a)}{1+\sum_{b\in\mathtt{Att}(a)}HC_{i-1}(b)}&\text{otherwise}\end{cases}$

The next semantics is the weighted max-based which considers the initial
weight of the argument as well as the highest acceptability degrees of its
attackers to determine the acceptability degree of the considered argument. In
this semantics, only the stronger attacker is considered and the number of
attackers is not used.

######  Definition 3.

The weighted max-based semantics, denoted $\sigma_{MB}$, is the function that
takes as input any weighted argumentation framework
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ and returns the function
$\sigma^{\mathcal{F}}_{MB}:A\to[0,1]$ such that for all
$a\in\mathcal{A},\sigma^{\mathcal{F}}_{MB}(a)=MB_{\infty}(a)$, where:

$MB_{i}(a)=\begin{cases}w(a)&\text{if }i=0\\\
\frac{w(a)}{1+max_{b\in\mathtt{Att}(a)}MB_{i-1}(b)}&\text{otherwise}\end{cases}$

The last semantics studied in this paper is the weighted card-based which
considers the initial weight of the argument, the number of its attackers as
well as the sum of the acceptability degrees of its attackers to determine the
acceptability degree of the considered argument. In this semantics, the number
of attackers is the most important factor to determine the acceptability
degree of an argument.

######  Definition 4.

The weighted card-based semantics, denoted $\sigma_{CB}$, is the function that
takes as input any weighted argumentation framework
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ and returns the function
$\sigma^{\mathcal{F}}_{CB}:A\to[0,1]$ such that for all
$a\in\mathcal{A},\sigma^{\mathcal{F}}_{CB}(a)=CB_{\infty}(a)$, where:

$CB_{i}(a)=\begin{cases}w(a)&\text{if }i=0\\\
\frac{w(a)}{1+|\mathtt{Att}^{*}(a)|+\frac{\sum_{b\in\mathtt{Att}^{*}(a)}CB_{i-1}(b)}{|\mathtt{Att}^{*}(a)|}}&\text{otherwise}\end{cases}$

Note that by convention, if $|\mathtt{Att}^{*}(a)|=0$, then we set
$CB_{i}(a)=\frac{\sum_{b\in\mathtt{Att}^{*}(a)}CB_{i-1}(b)}{|\mathtt{Att}^{*}(a)|}=0$.

We note in passing that the properties for these semantics have been
researched in depth by Amgoud et al. in [21]. Perhaps the most important
property, in the context of this paper, is the convergence of the
$\sigma_{HC},\sigma_{MB}$ and $\sigma_{CB}$ semantics for finite frameworks
(see Theorem 7, 12, 17 in [21]). A proof of convergence for a broader class of
semantics (including these three) was proved in the work of Oren et al. [26].
This means that for any given argumentation framework, semantics and initial
weights, the final acceptability degrees of all arguments can always be
computed.

######  Example 1.

An agent may believe the following arguments.

  * $a_{0}$:

Tomatoes older than a week can go rotten; these tomatoes are a week and a half
old.

  * $a_{1}$:

Tomatoes kept in the fridge (like these ones) can last longer than a week, and
so the tomatoes are not rotten.

  * $a_{2}$:

My friend ate one of the tomatoes this morning, and it tasted fine, therefore
they are not rotten.

  * $a_{3}$:

My friend is not very good at discriminating whether something is rotten by
taste, so the tomatoes might be rotten.

Here, $a_{0}$ is attacked by $a_{1}$ and $a_{2}$, while the latter is attacked
by $a_{3}$. The agent ascribes each argument with an initial weight encoding
the agent’s belief in the applicability or strength of the argument, i.e.,
$w(a_{0})=0.9$, $w(a_{1})=0.7$, $w(a_{2})=0.7$, and $w(a_{3})=0.6$. Fig. 2
illustrates this weighted argumentation framework
$\mathcal{F}=\langle\\{a_{0},a_{1},a_{2},a_{3}\\},\\{(a_{1},a_{0}),(a_{2},a_{0}),(a_{3},a_{2})\\},w\rangle$.

Figure 2: The weighted argumentation framework from Example 1.

We consider three different semantics in this paper (defined above); yielding
the final acceptability degrees in Table 1. In turn, a reasoner using the
weighted h-categoriser semantics $\sigma_{HC}$ or $\sigma_{CB}$ semantics
would have preferences $a_{1}\succ a_{3}\succ a_{2}\succ a_{0}$, while if it
were to use $\sigma_{MB}$ preferences would be $a_{1}\succ a_{3}\succ
a_{0}\succ a_{2}$. Note that while the $\sigma_{HC}$ and $\sigma_{CB}$
semantics yield similar preference orderings, the agent would be less sure of
its conclusions in the latter case (due to the smaller difference in weights).

Argument | $\sigma_{HC}^{\mathcal{F}}(a_{i})$ | $\sigma_{MB}^{\mathcal{F}}(a_{i})$ | $\sigma_{CB}^{\mathcal{F}}(a_{i})$
---|---|---|---
$a_{0}$ | 0.421 | 0.529 | 0.258
$a_{1}$ | 0.7 | 0.7 | 0.7
$a_{2}$ | 0.438 | 0.438 | 0.269
$a_{3}$ | 0.6 | 0.6 | 0.6
Table 1:  Final acceptability degrees for each argument of Example 1 (Fig. 2)
for $\sigma_{HC},\sigma_{MB},$ and $\sigma_{CB}$.

##  3 Inferring Attacks

In this paper, we focus on the problem of identifying whether we can infer
suitable attacks between arguments given their initial weights and desirable
final acceptability degrees (as shown at the bottom of Fig. 1). However, we
ground most of our discussion in the closely related decision problem. Given a
gradual argumentation semantics, a set of arguments, and associated
information about these arguments (i.e., initial weights and some or all
desirable final acceptability degrees), can we determine the attacks between
arguments that — according to the semantics — lead to the desirable final
acceptability degrees from the initial weights.

In this section, we consider the _complete problem_ , where the initial
weights and desirable final acceptability degrees for _all_ arguments are
known. We formalise this problem as follows.

######  Problem 1.

The decision problem $\mathcal{DEC}^{x}_{c}$ is: _Given a set of arguments
$\mathcal{A}$, a gradual semantics $\sigma_{x}$, a weighting function $w$, and
a total desired final acceptability degree function $S:\mathcal{A}\to[0,1]$,
is there a set of attacks $\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$
such that for all $a\in\mathcal{A},\sigma^{\mathcal{F}}_{x}(a)=S(a)$, where
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$?_

We investigate this decision problem for the three gradual semantics
$\sigma_{x}$, for $x\in\\{HC,CB,MB\\}.$

######  Proposition 1.

$\mathcal{DEC}_{c}^{MB}$ is polynomial and can be decided in $O(n)$ time and
space.

###### Proof.

We create the set $L=\\{1+S(b)\mid b\in\mathcal{A}\\}$, for which an $O(1)$
lookup can be performed. We can then use the following trivial algorithm to
solve $\mathcal{DEC}_{c}^{MB}$:

1:for all $a\in\mathcal{A}$ do

2: if ($w(a)=0$ and $S(a)\neq 0$) or ($w(a)\neq 0$ and $S(a)=0$) then

3: return False $\triangleright$ A zero initial weight cannot lead to a non-
zero final acceptability degree (and vice-versa).

4: end if

5: if $S(a)\neq 0$ and $w(a)/S(a)\notin L$ then

6: return False $\triangleright$ Contradiction by definition of the
$\sigma_{MB}$ semantics.

7: end if

8:end for

9:return True

∎

In the algorithm above, line 2 checks whether arguments with zero (resp. non-
zero) initial weights and non-zero (resp. zero) desired final acceptability
degrees exist; the presence of such arguments would mean that the weighted-
max-based semantics cannot be satisfied (line 3). Line 5 then checks the
existence of an attacking argument with a suitable acceptability degree (via a
lookup in the set $L$) to satisfy the weighted-max-based semantics in $O(1)$
time. Since lines 1-8 iterate over all arguments, the time complexity is
$O(n)$; similarly, storing $L$ takes $O(n)$ space.

$a_{0}$1$\frac{nm^{*}}{0.4T+nm^{*}}$$a_{1}$$\frac{0.4m_{1}}{nm^{*}}$$a_{2}$$\frac{0.4m_{2}}{nm^{*}}$$a_{n}$$\frac{0.4m_{n}}{nm^{*}}$$\vdots$$m_{1}$$m_{2}$$m_{n}$$T$
Figure 3: Graphical representation of the polynomial transformation (dashed
lines) of an $\mathcal{SSP}$ instance (rectangular nodes) into an instance of
$\mathcal{DEC}_{c}^{HC}$ (circular nodes). The initial weight of $a_{0}$ is 1
(shown in black above $a_{0}$), and of $a_{1}$ to $a_{n}$, is equal to their
final acceptability degree (where final acceptability degrees are shown in
blue). The initial weights of the latter arguments have thus been omitted.

######  Proposition 2.

$\mathcal{DEC}_{c}^{HC}$ is NP-complete.

###### Proof.

We show that $\mathcal{DEC}_{c}^{HC}$ is NP-complete using the subset-sum
problem ($\mathcal{SSP}$). Formally, $\mathcal{SSP}$ is defined as answering
the following question. Consider a multiset of positive numbers $M$ and a
number $T\in\mathbb{R}^{+}$, is there a subset $M^{\prime}\subseteq M$ such
that $\sum\limits_{m^{\prime}\in M^{\prime}}m^{\prime}=T$?

To prove $\mathcal{DEC}_{c}^{HC}$ is NP-complete we must demonstrate that it
is in NP and identify a polynomial time reduction from $\mathcal{SSP}$ to
$\mathcal{DEC}_{c}^{HC}$.

To demonstrate that $\mathcal{DEC}_{c}^{HC}$ belongs to NP we observe that the
certificate of the problem is a set of attacks. Given a set of attacks, we can
check in polynomial time whether
$S(a)=w(a)/(1+\sum_{b\in\mathtt{Att}(a)}S(b))$ for all $a\in\mathcal{A}$ (as
we have all initial weights and the desired final acceptability degrees),
therefore the problem is in NP.

Turning to the reduction, we begin by reducing $\mathcal{SSP}$ to
$\mathcal{DEC}_{c}^{HC}$. Let us assume we have a multi-set of positive
numbers $M=\\{m_{1},\dots,m_{n}\\}$ and $T\in\mathbb{R}^{+}$. We denote
$\sum_{i}m_{i}$ by $m^{*}$. We then create a set of $n+1$ arguments
$\mathcal{A}=\\{a_{0},a_{1},a_{2},\dots,a_{n}\\}$ such that for all
$i\in\\{1,\dots,n\\}$, $S(a_{i})=w(a_{i})=(0.4m_{i})/(nm^{*})$, and we set
$w(a_{0})=1$ and $S(a_{0})=nm^{*}/(0.4T+nm^{*})$. This transformation is
represented in Fig. 3.

######  Example 2.

Consider the $\mathcal{SSP}$ instance where $T=100$ and
$M=\\{23,94,1,37,40\\}$. Here, $n=5$ and $m^{*}=195$. Using our
transformation, we obtain the arguments, initial weights, and final
acceptability degrees shown in Table 2.

Argument | Initial | Desired final
---|---|---
| Weight | acceptability degree
$a_{0}$ | 1 | 0.96059
$a_{1}$ | 0.00944
$a_{2}$ | 0.03856
$a_{3}$ | 0.00041
$a_{4}$ | 0.01518
$a_{5}$ | 0.01641
Table 2:  The arguments created from Example 2 using the reduction described
in Proposition 2.

  * •

We now demonstrate that — using the above reduction — a solution to
$\mathcal{SSP}$ exists only if a solution to $\mathcal{DEC}_{c}^{HC}$ exists.
If there exists an $M^{\prime}\subseteq M$ such that
$\sum\limits_{m^{\prime}\in M^{\prime}}m^{\prime}=T$, then
$\mathcal{D}=\\{(f(m),a_{0})\mid m\in M^{\prime}\\}$ is a set of attacks such
that for all $a\in\mathcal{A},\sigma^{\mathcal{F}}(a)=S(a)$, where $f$
associates the corresponding argument and
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$. Indeed, we have for all
$i\in\\{1,\dots,n\\},\sigma^{\mathcal{F}}_{HC}(a_{i})=S(a_{i})$ since $a_{i}$
is not attacked and:

$\displaystyle\sigma^{\mathcal{F}}_{HC}(a_{0})$
$\displaystyle=\frac{1}{1+\sum_{m\in M^{\prime}}S(f(m))}$
$\displaystyle=\frac{1}{1+\frac{0.4T}{nm^{*}}}$
$\displaystyle=\frac{nm^{*}}{nm^{*}+0.4T}$ $\displaystyle=S(a_{0})$

  * •

We now show the reduction in the other direction — a solution to
$\mathcal{DEC}_{c}^{HC}$ exists only if a solution to $\mathcal{SSP}$ can be
found via the above reduction. If there exists
$\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$ such that for all
$b\in\mathcal{A},\sigma^{\mathcal{F}}(b)=S(b)$, then
$M^{\prime}=\\{(S(b)nm^{*})/0.4\mid(b,a_{0})\in\mathcal{D}\\}\subseteq M$ is
such that $\sum\limits_{m^{\prime}\in M^{\prime}}m^{\prime}=T$, where
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$. Indeed:

$\displaystyle\sum\limits_{m^{\prime}\in M^{\prime}}m^{\prime}$
$\displaystyle=\left(\sum\limits_{(b,a_{0})\in\mathcal{D}}S(b)\right)\frac{nm^{*}}{0.4}$
$\displaystyle=\left(\sum\limits_{(b,a_{0})\in\mathcal{D}}\sigma^{\mathcal{F}}_{HC}(b)\right)\frac{nm^{*}}{0.4}$
$\displaystyle=\left(\frac{1}{\frac{nm^{*}}{0.4T+nm^{*}}}-1\right)\frac{nm^{*}}{0.4}$
$\displaystyle=\left(\frac{0.4T}{nm^{*}}\right)\frac{nm^{*}}{0.4}$
$\displaystyle=T$

Note that $(a_{0},a_{0})\notin\mathcal{D}$. Indeed, if
$(a_{0},a_{0})\in\mathcal{D}$ then we have that
$\sigma_{HC}^{\mathcal{F}}(a_{0})=1/(1+\sigma_{HC}^{\mathcal{F}}(a_{0})+Y)$,
where $Y=\sum_{b\in
Att(a_{0})\setminus\\{a_{0}\\}}\sigma_{HC}^{\mathcal{F}}(b)$. Hence,
($\sigma_{HC}^{\mathcal{F}}(a_{0})^{2}+\sigma_{HC}^{\mathcal{F}}(a_{0})-1)/(-\sigma_{HC}^{\mathcal{F}}(a_{0}))=Y$
and since $Y\geq 0$, we conclude that
$0\leq\sigma_{HC}^{\mathcal{F}}(a_{0})\leq\frac{-1+\sqrt{5}}{2}\simeq 0.618$.
However, we get a contradiction as $S(a_{0})=\sigma_{HC}^{\mathcal{F}}(a_{0})$
and:

$\displaystyle\frac{T}{nm^{*}}$ $\displaystyle\leq 1$
$\displaystyle\frac{0.4T}{nm^{*}}$ $\displaystyle\leq 0.4$
$\displaystyle\frac{0.4T+nm^{*}}{nm^{*}}$ $\displaystyle\leq 1.4$
$\displaystyle S(a_{0})$ $\displaystyle\geq 0.714$

We have proved that $\mathcal{DEC}_{c}^{HC}$ is in NP and that $\mathcal{SSP}$
is polynomial time reducible to $\mathcal{DEC}_{c}^{HC}$ (the size of the
argumentation framework produced is polynomial with respect to the size of the
$\mathcal{SSP}$ instance), therefore $\mathcal{DEC}_{c}^{HC}$ is NP-complete.
∎

######  Example 3 (Cont’d Example 2).

We see that the subset sum problem has a solution (using values 23,37 and 40).
Analogously, a solution to $\mathcal{DEC}_{c}^{HC}$ exists by having arguments
$a_{1},a_{4}$ and $a_{5}$ attack argument $a_{0}$, as shown in Fig. 4.

$a_{0}$10.96059$a_{1}$0.00944$a_{2}$0.03856$a_{3}$0.00041$a_{4}$0.01518$a_{5}$0.01641239413740100
Figure 4: Representation of how a solution to an $\mathcal{SSP}$ instance
(represented with the gray rectangles) can be obtained from a solution to a
corresponding instance from $\mathcal{DEC}^{HC}_{c}$ (the attacks drawn). Blue
values for $a_{1}\ldots a_{5}$ indicate both inital weights and final
acceptability degrees, and denote final acceptability degrees for $a_{0}$,
which has an initial weight of 1.

######  Proposition 3.

$\mathcal{DEC}_{c}^{CB}$ is NP-complete.

###### Proof.

Similar to the previous proof, we show that $\mathcal{DEC}_{c}^{CB}$ is NP-
complete using the $k$-subset-sum problem ($k\mathcal{SSP}$). Formally,
$k\mathcal{SSP}$ is defined as answering the following question. Consider a
multiset of positive numbers $M$ and a number $T\in\mathbb{R}^{+}$, is there a
subset $M^{\prime}\subseteq M$ such that $\sum_{m^{\prime}\in
M^{\prime}}m^{\prime}=T$ and $|M^{\prime}|=k$?

We first observe that the certificate of the problem $\mathcal{DEC}_{c}^{CB}$
is a set of attacks. Given a set of attacks, we can check in polynomial time
whether
$S(a)=w(a)/(1+|\mathtt{Att}^{*}(a)|+\sum_{b\in\mathtt{Att}^{*}(a)}S(b)/|\mathtt{Att}^{*}(a)|)$
for all $a\in\mathcal{A}$, meaning that the problem is in NP.

We now reduce $k\mathcal{SSP}$ to $\mathcal{DEC}_{c}^{CB}$. Let us assume we
have a multi-set of positive numbers $M=\\{m_{1},\dots,m_{n}\\}$, $1\leq k\leq
n$, and $T\in\mathbb{R}^{+}$. We denote by $m^{*}=\max_{m_{i}\in M}m_{i}$ and
$u=\frac{\sqrt{k^{2}+2k+4/k+1}-k-1}{3}$ (note that $u\in]0,(2\sqrt{2}-2)/3]$
when $k\geq 1$). We create $n+1$ arguments
$\mathcal{A}=\\{a_{0},a_{1},a_{2},\dots,a_{n}\\}$ such that for all
$i\in\\{1,\dots,n\\},S(a_{i})=w(a_{i})=um_{i}/m^{*}$ and we set $w(a_{0})=1$
and $S(a_{0})=1/(1+k+Tu/(km^{*}))$.

  * •

If there exists an $M^{\prime}\subseteq M$ such that $\sum_{m^{\prime}\in
M^{\prime}}m^{\prime}=T$ and $|M^{\prime}|=k$, then
$\mathcal{D}=\\{(f(m),a_{0})|m\in M^{\prime}\\}$ is a set of $k$ attacks such
that for all $a\in\mathcal{A},\sigma^{\mathcal{F}}(a)=S(a),$ where
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$. Indeed, we have for all
$i\in\\{1,\dots,n\\},\sigma_{CB}^{\mathcal{F}}(a_{i})=S(a_{i})$ since $a_{i}$
is not attacked and:

$\displaystyle\sigma_{CB}^{\mathcal{F}}(a_{0})$
$\displaystyle=\frac{1}{1+k+\frac{\sum_{m\in M^{\prime}}S(f(m))}{k}}$
$\displaystyle=\frac{1}{1+k+\frac{\frac{Tu}{m^{*}}}{k}}$
$\displaystyle=\frac{1}{1+k+\frac{Tu}{km^{*}}}$

  * •

Assume we have a solution to $\mathcal{DEC}_{c}^{CB}$, i.e. we have
$\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$ such that for all
$b\in\mathcal{A},\sigma^{\mathcal{F}}(b)=S(b)$. We know that $a_{0}$ is
attacked by $k$ arguments in $\mathcal{D}$ as its value lies between
$[1/(k+2),1/(k+1)]$ and that arguments $a_{1}$ to $a_{n}$ are not attacked
(except if they or their attackers have initial weights of $0$). We can build
$M^{\prime}=\\{S(b)*m^{*}/u|(b,a_{0})\in\mathcal{D}\\}\subseteq M$ such that
$|M^{\prime}|=k$ and $\sum_{m^{\prime}\in M^{\prime}}m^{\prime}=T$. Indeed:

$\displaystyle\sum_{m^{\prime}\in M^{\prime}}m^{\prime}$
$\displaystyle=\left(\sum_{(b,a_{0})\in\mathcal{D}}S(b)\right)\frac{m^{*}}{u}$
$\displaystyle=\left(\frac{Tu}{m^{*}}\right)\frac{m^{*}}{u}$ $\displaystyle=T$

We show that $(a_{0},a_{0})\notin\mathcal{D}$ by contradiction. Assume we have
this self-attack, then the maximum value with self attack possible for
$\sigma_{CB}^{\mathcal{F}}(a_{0})$ is determined by computing the unique
fixed-point of the function $f(x)=1/(1+k+x/k)$ which is:

$0<\frac{-k^{2}+\sqrt{k(k^{3}+2k^{2}+k+4)}-k}{2}\leq 1$

Moreover, it holds that:

$\displaystyle\frac{-k^{2}+\sqrt{k(k^{3}+2k^{2}+k+4)}-k}{2}$
$\displaystyle<\frac{1}{1+k+u}$
$\displaystyle<\frac{1}{1+k+\frac{Tu}{km^{*}}}$ $\displaystyle<S(a_{0})$

This is a contradiction with $S(a_{0})=\sigma_{CB}^{\mathcal{F}}(a_{0})$.

∎

To recap, our results show that $\mathcal{DEC}^{MB}_{c}$ is polynomial (and
indeed, can be solved in linear time), while $\mathcal{DEC}^{HB}_{c}$ and
$\mathcal{DEC}^{CB}_{c}$ are both NP-complete. This latter result was obtained
by a reduction to a variant of the subset-sum problem.

##  4 Identifying Solutions

Rather than simply considering the decision problem, it is useful — if
possible — to be able to infer the attacks induced by some set of initial
weights and final acceptability degrees. We consider each semantics
individually.

###  4.1 The Weighted Max-based Semantics

For the weighted max-based semantics, it is trivial to modify the algorithm
from Proposition 1 to infer a suitable set of attacks (when possible). Rather
than simply returning True or False, we return, by modifying lines 5 and 6,
any set of attacks $X$ that satisfy the condition that for all
$a\in\mathcal{A}$, there exists $(x,a)\in X$ such that $w(a)/S(a)=(1+S(x))$.
Thus, we note that this semantics does little to constrain the attacks in the
framework. If we discover that there is an attack from argument $a_{i}$ to
argument $a_{0}$ in a solution, then under the max-based semantics, we can
expand this solution by adding additional attacks from any argument $a_{j}$ to
$a_{0}$, where $S(a_{j})\leq S(a_{i})$, without affecting the result.

######  Proposition 4 (Solution Expansion).

Given a set of arguments $\mathcal{A}$, a weighting function
$w:\mathcal{A}\to[0,1]$, and a desirable final acceptability degree function
$S:\mathcal{A}\to[0,1]$. If $\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$
is such that for all $a\in\mathcal{A}$, $\sigma_{MB}^{\mathcal{F}}(a)=S(a)$,
where $\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ then for all
$a\in\mathcal{A},\sigma_{MB}^{\mathcal{F}^{\prime}}(a)=S(a)$, where
$\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle,\mathcal{D}^{\prime}=\mathcal{D}\cup
X$ and $X\subseteq\\{(a_{i},a_{j})\mid\exists(a_{k},a_{j})\in\mathcal{D}$ and
$S(a_{i})\leq S(a_{k})\\}\cup\\{(a_{i},a_{j})\mid w(a_{j})=0\\}$. We say that
$\mathcal{D}^{\prime}$ is an expansion of $\mathcal{D}$.

Similarly, if we have a set of attacks that achieve the desirable final
acceptability degrees for all arguments and there is an attack from $a_{i}$ to
$a_{0}$, then under the max-based semantics, we can contract this solution by
removing attacks from any other argument $a_{j}$ to $a_{0}$, where
$S(a_{j})\leq S(a_{i})$.

######  Proposition 5 (Solution Contraction).

Given a set of arguments $\mathcal{A}$, a weighting function
$w:\mathcal{A}\to[0,1]$, and a desirable final acceptability degree function
$S:\mathcal{A}\to[0,1]$. If $\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$
is such that for all $a\in\mathcal{A}$, $\sigma_{MB}^{\mathcal{F}}(a)=S(a)$,
where $\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ then for all
$a\in\mathcal{A},\sigma_{MB}^{\mathcal{F}^{\prime}}(a)=S(a)$, where
$(a_{i},a_{0})\in\mathcal{D},\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle,\mathcal{D}^{\prime}=\mathcal{D}\setminus
X$ and $X\subseteq\\{(a_{j},a_{0})\in\mathcal{D}\mid a_{j}\neq a_{i}$ and
$S(a_{j})\leq S(a_{i})\\}\cup\\{(a_{j},a_{0})|w(a_{0})=0\\}$. We say that
$\mathcal{D}^{\prime}$ is a contraction of $\mathcal{D}$ (on
$(a_{i},a_{0})\in\mathcal{D}$).

Figure 5: The argumentation framework of Example 4.

######  Example 4.

Let us consider $\mathcal{A}$, $w$, $\mathcal{D}$ as shown in Figure 5 and the
desirable final acceptability degree function $S$ such that $S(a_{0})=0.43$,
$S(a_{1})=0.30$, $S(a_{2})=0.58$, and $S(a_{3})=0.30$. A contraction
$\mathcal{D}^{\prime}$ of $\mathcal{D}$ on $(a_{2},a_{2})$ will remove the
attacks $(a_{0},a_{2}),(a_{1},a_{2})$, and $(a_{3},a_{2})$ from $\mathcal{D}$
without changing the acceptability degrees under the max-based semantics.
Likewise, an expansion $\mathcal{D}^{\prime\prime}$ of $\mathcal{D}^{\prime}$
can be obtained by adding the attack $(a_{0},a_{2})$ as this does not change
the acceptability degrees. This is represented in Fig. 6.

Figure 6:  Representation of
$\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle$
(left), where $\mathcal{D}^{\prime}$ is a contraction of $\mathcal{D}$ on
$(a_{2},a_{2})$ and
$\mathcal{F}^{\prime\prime}=\langle\mathcal{A},\mathcal{D}^{\prime\prime},w\rangle$
(right), where $\mathcal{D}^{\prime\prime}$ is an expansion of
$\mathcal{D}^{\prime}$.

Once a solution for the max-based semantics is found, we can reach all the
other solutions by expanding this initial solution once and then successively
contracting it.

######  Proposition 6.

Given a set of arguments $\mathcal{A}$, a weighting function
$w:\mathcal{A}\to[0,1]$, and a desirable final acceptability degree function
$S:\mathcal{A}\to[0,1]$. If
$\mathcal{D},\mathcal{D}^{\prime}\subseteq\mathcal{A}\times\mathcal{A}$ are
such that for all $a\in\mathcal{A}$, $\sigma_{MB}^{\mathcal{F}}(a)=S(a)$,
$\sigma_{MB}^{\mathcal{F}^{\prime}}(a)=S(a)$ where
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ and
$\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle$ then
there exists $\mathcal{D}^{*}\subseteq\mathcal{A}\times\mathcal{A}$, such that
$\mathcal{D}^{*}$ is an expansion of $\mathcal{D}$, and a sequence of sets of
attacks $(\mathcal{D}_{1},\mathcal{D}_{2},\dots,\mathcal{D}_{n})$, where
$\mathcal{D}_{1}=\mathcal{D}^{*}$, $\mathcal{D}_{n}=\mathcal{D}^{\prime}$ and
for all $1\leq i\leq n-1,\mathcal{D}_{i+1}$ is a contraction of
$\mathcal{D}_{i}$.

###### Proof.

Let us consider $\mathcal{A}=\\{a_{1},a_{2},\dots,a_{n}\\}$ and two arbitrary
solutions
$\mathcal{D},\mathcal{D}^{\prime}\subseteq\mathcal{A}\times\mathcal{A}$ for
$\mathcal{DEC}_{c}^{MB}$. We prove this proposition by construction. By
definition, for all
$a\in\mathcal{A},\sigma_{MB}^{\mathcal{F}}(a)=\sigma_{MB}^{\mathcal{F}^{\prime}}(a)=S(a)$,
where $\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$ and
$\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle$. This
means that for all $a\in\mathcal{A}$, such that $w(a)\neq
0,\max_{b\in\mathtt{Att}_{\mathcal{F}}(a)}S(b)=\max_{b\in\mathtt{Att}_{\mathcal{F}^{\prime}}(a)}S(b)$.
Thus, $\mathcal{D}^{*}=\mathcal{D}\cup\mathcal{D}^{\prime}$ is an expansion of
$\mathcal{D}$. Then, for all $1\leq i\leq n$, it holds that
$\mathcal{D}_{i+1}=\mathcal{D}_{i}\setminus\\{(a_{j},a_{i})\in\mathcal{D}|(a_{j},a_{i})\notin\mathcal{D}^{\prime}\\}$
is a contraction of $\mathcal{D}_{i}$, where
$\mathcal{D}_{1}=\mathcal{D}^{*}$. It is clear that
$\mathcal{D}_{n+1}=\mathcal{D}^{\prime}$ as all attacks in
$\mathcal{D}\setminus\mathcal{D}^{\prime}$ have been removed from
$\mathcal{D}^{*}$. ∎

###  4.2 The Weighted H-Categoriser Semantics

Let us consider the case of the weighted h-categoriser semantics. Given an
input $\mathcal{A}=\\{a_{1},\dots,a_{n}\\}$, an initial weight function $w$,
and a desirable final acceptability degree function $S$; we seek a set of
attacks $\mathcal{D}\subseteq\mathcal{A}\times\mathcal{A}$ such that for all
$a\in\mathcal{A},\sigma_{HC}^{\mathcal{F}}(a)=S(a)$, where
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$.

Recall from the definition of the weighted h-categoriser semantics that any
solution must mean that the following equation holds.

$S(a_{i})=\frac{w(a_{i})}{1+\sum_{b\in\mathtt{Att}(a_{i})}S(b)}$

Moreover, if $w(a_{i})\neq 0$, we can rearrange the previous equation to
obtain:

$\sum_{b\in\mathtt{Att}(a_{i})}S(b)=\frac{w(a_{i})-S(a_{i})}{S(a_{i})}$

For the complete problem, we are given $w(a_{i})$ and $S(a_{i})$ for all
$a_{i}\in\mathcal{A}$, allowing us to compute
$\sum_{b\in\mathtt{Att}(a_{i})}S(b)$ via the above equation. In other words,
for every argument $a_{i}$, we can compute a target value
$T=\sum_{b\in\mathtt{Att}(a_{i})}S(b)$ for which the final acceptability
degrees of all its attackers must sum up to. By considering the multi-set
$M=\\{S(a_{j})\mid a_{j}\in\mathcal{A}\\}$, we must solve a single subset-sum
problem to identify the attackers for a single argument $a_{i}$. Extending
this to all $n=|\mathcal{A}|$ arguments in our framework, we can therefore
identify all attacks in the framework by solving $n$ versions of the subset-
sum problem. Algorithm 1 provides the pseudo-code for this approach.

1:$\mathcal{A}$ a set of arguments

2:$w:\mathcal{A}\to[0,1]$ the initial weights for each argument

3:$S:\mathcal{A}\to[0,1]$ the desired final acceptability degrees for each
argument

4:function SolveHC($\mathcal{A},w,S$)

5: $D=\\{\\}$

6: $M\leftarrow\\{S(b)|b\in\mathcal{A}\\}$

7: for all $a\in\mathcal{A}$ do

8: if ($w(a)=0$ and $S(a)\neq 0$) or ($w(a)\neq 0$ and $S(a)=0$) then

9: return False

10: end if

11: if $w(a)\neq 0$ and $w(a)\neq S(a)$ then

12: $T\leftarrow\frac{w(a)-S(a)}{S(a)}$

13: if SSP($T,M$) = False then

14: return False

15: end if

16: $D=D\cup\\{(b,a)|S(b)\in$SSP($T,M$)$\\}$

17: end if

18: end for

19: return $D$

20:end function

Algorithm 1 Procedure to solve $\mathcal{DEC}_{c}^{HC}$. SSP (line 13, 16)
calls a subset-sum solver which returns the elements of $M$ that sum up to
$T$, or False if no such elements can be found.

We note in passing that the standard version of the subset-sum problem assumes
that $T$ and elements of $M$ are all integers. If we assume that all initial
weights and final acceptability degrees are rational, we can easily transform
our computed $T$ and $M$ values to integers. The most common — dynamic
programming — approach to solving standard subset-sum can run in pseudo-
polynomial time. However, the integers we obtain become very large very
quickly, making this approach impractical. Future work will consider using
state-of-the-art techniques for solving subset-sum over real numbers instead,
e.g. the recent FPTAS of Costandin [27]. In addition, having transformed our
problem to an instance of the subset-sum problem opens up the possibility of
transforming the problem to other NP-complete problems for which efficient
solvers exist, such as satisfiability.

Moreover, once a set of attacks is found to be a solution, we can obtain other
solutions by replacing the attacks to a single argument $x$ by other attacks
to this argument so that the sum of the degree of the attackers remains the
same. Given the simplicity of this proposition, we do not provide a proof for
it here.

######  Proposition 7.

Consider two weighted argumentation frameworks
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle$,
$\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle$, and a
desirable final acceptability degree function $S:\mathcal{A}\to[0,1]$ such
that $\sigma^{\mathcal{F}}_{HC}(a)=S(a)$ for any $a\in\mathcal{A}$. If all of
the following hold

  * •

$x\in\mathcal{A}$

  * •

$Z\subseteq\mathcal{A}\times\\{x\\}$

  * •

$\sum_{(z,x)\in Z}S(z)=(w(x)-S(x))/S(x)$ if $w(x)\neq 0$

  * •

$\mathcal{D}^{\prime}=(\mathcal{D}\cap(\mathcal{A}\times(a\setminus\\{x\\})))\cup
Z$

then for all $a\in\mathcal{A},\sigma^{\mathcal{F}^{\prime}}_{HC}(a)=S(a)$.

###  4.3 The Weighted Cardinality-based Semantics

We can adopt a similar approach for $\sigma_{CB}$ as was done for
$\sigma_{HC}$. We begin by assuming that there are $k$ attacks from arguments
with non-zero initial weight against an argument $a_{i}$. Any solution must
mean that the following equation holds:

$S(a_{i})=\frac{w(a_{i})}{1+k+\frac{1}{k}\sum_{b\in\mathtt{Att}(a_{i})}S(b)}$

If $w(a_{i})\neq 0$, rearranging gives us the equation:

$\sum_{b\in\mathtt{Att}(a_{i})}S(b)=-\frac{k(S(a_{i})k+S(a_{i})-w(a_{i}))}{S(a_{i})}$

Again, all values on the right-hand side of the equation are given for the
complete problem given, allowing us to compute the value of the left-hand side
for each argument. Assuming a non-zero number of attacks, while we could
(naively) iterate over all $k=1\ldots n$ to identify the number of attacks
against an argument, and thereby determine $k$, we observe that if
$S(b)=\epsilon>0$, $\lim{\epsilon}\to 0$, for all $b\in\mathtt{Att}(a_{i})$
the semantic equation reduces to the following.

$S(a_{i})=\frac{w(a_{i})}{1+k}$

Solving for $k$, we see that:

$k=\frac{w(a_{i})-S(a_{i})}{S(a_{i})}$

Now assume instead that $S(b)=1$ for all $b\in\mathtt{Att}(a_{i})$. Performing
the same operations means that:

$k=\frac{w(a_{i})-2S(a_{i})}{S(a_{i})}$

These two equations serve as an upper and lower bound for $k$. Since $k$ must
be an integer, we can avoid the need to iterate over the number of attacks by
computing $k$ as follows.

$k=\lfloor\frac{w(a_{i})-S(a_{i})}{S(a_{i})}\rfloor=\lceil\frac{w(a_{i})-2S(a_{i})}{S(a_{i})}\rceil$

The pseudo-code for this approach is described in Algorithm 2.

1:$\mathcal{A}$ a set of arguments

2:$w:\mathcal{A}\to\mathbb{Q}$ the initial weights for each argument

3:$S:\mathcal{A}\to\mathbb{Q}$ the final acceptability degree for each
argument

4:function SolveCB($\mathcal{A},w,S$)

5: $D=\\{\\}$

6: $M\leftarrow\\{S(b)|b\in\mathcal{A}\\}$

7: for all $a\in\mathcal{A}$ do

8: if ($w(a)=0$ and $S(a)\neq 0$) or ($w(a)\neq 0$ and $S(a)=0$) then

9: return False

10: end if

11: if $w(a)\neq 0$ and $w(a)\neq S(a)$ then

12: $k\leftarrow\lfloor\frac{w(a)-S(a)}{S(a)}\rfloor$

13: $T\leftarrow-\frac{k(S(a)k+S(a)-w(a))}{S(a)}$

14: if kSSP($T,M,k$) = False then

15: return False

16: end if

17: $D\leftarrow D\cup\\{(b,a)|S(b)\in$kSSP($T,M,k$)$\\}$

18: end if

19: end for

20: return $D$

21:end function

Algorithm 2 Procedure to solve $\mathcal{DEC}_{c}^{CB}$. kSSP (line 14, 17)
calls a subset-sum solver which returns $k$ elements of $M$ which sum up to
$T$.

Since $k$ is known, the $k\mathcal{SSP}$ solver called in Algorithm 2 could
potentially be more efficient than that used in the h-categoriser semantics.

Analogous to the result from Proposition 7, under the cardinality semantics,
once a set of attacks is found to be a solution, we can obtain other solutions
by replacing the $k$ attacks on a single argument $x$ by another set of $k$
attacks to this argument so that the sum of the final acceptability degree of
the attackers remains the same. Given the simplicity of this proposition, we
do not provide a proof for it here.

######  Proposition 8.

Given two weighted argumentation frameworks
$\mathcal{F}=\langle\mathcal{A},\mathcal{D},w\rangle,\mathcal{F}^{\prime}=\langle\mathcal{A},\mathcal{D}^{\prime},w\rangle$,
and a desirable final acceptability degree function $S:\mathcal{A}\to[0,1]$
such that for all $a\in\mathcal{A}$, $\sigma_{CB}^{\mathcal{F}}(a)=S(a)$. If
all the following hold:

  * •

$x\in\mathcal{A}$

  * •

$Z\subseteq\mathcal{A}\times\\{x\\}$, and

  * •

$\mathcal{D}^{\prime}=\left(\mathcal{D}\cap(\mathcal{A}\times(\mathcal{A}\setminus\\{x\\}))\right)\cup
Z$,

  * •

$|Z|=\lfloor\frac{w(a)-S(a)}{S(a)}\rfloor$ and $\sum_{(z,x)\in
Z}S(z)=-\frac{k(S(x)k+S(x)-w(x))}{S(x)}$ if $w(x)\neq 0$.

then for all $a\in\mathcal{A}$, it is the case that
$\sigma_{CB}^{\mathcal{F}^{\prime}}(a)=S(a)$

Propositions 4, 5, and 6 demonstrate that there are typically a large number
of non-minimal argumentation frameworks for the weighted max-based semantics.
For the weighted h-categoriser semantics, attacks can be substituted as long
as the sum of the final acceptability degrees of the attacking arguments match
(see Proposition 7), while for weighted cardinality semantics, attacks can
only be substituted by a set of attackers of the same size which final
acceptability degree sums to the same value (see Proposition 8). We also note
that, for all semantics, any argument with an initial weight of 0 can clearly
have any number of attacks against it.

##  5 Discussion and Future Work

To this point, we have considered only the complete problem of attack
inference in gradual argumentation frameworks, and we now briefly discuss the
partial problem. Here, we are given a semantics, a set of arguments, a partial
mapping between arguments and initial weights, and a partial mapping between
arguments and final acceptability degrees, and we must determine whether
attacks (and initial weights which were not provided) can be identified which
make the given final acceptability degrees consistent with the semantics.

Since the complete problem is a special case of this partial problem, and
since we can still verify correctness in polynomial time, the NP-completeness
results of Section 3 still apply to the $CB$ and $HC$ semantics. The behaviour
of the $MB$ version of the partial problem — which was polynomial in the
complete problem — is more challenging to characterise. While it is easy to
show that there are polynomial instances of the partial problem (e.g., when
all initial weights are given and all but one final acceptability degree is
provided), we strongly believe that the general case is NP-complete. We leave
proof of this result as an element of future work. Other directions for
research include providing a mapping from subset-sum to other problems for
which solvers exist (e.g., satisfiability) and evaluating the performance of
such solvers222An implementation of our algorithms using an optimised depth-
first-search SSP solver can be found at
https://github.com/jhudsy/Gradual_Attack_Inference. We do not provide
experimental data as the performance of our solver demonstrates the
exponential growth of the underlying subset-sum problem. Systems with more
than $\sim$13 arguments can only rarely be solved in reasonable time using our
implementation.. Argumentation researchers have found that this approach has
often yielded excellent results [28]. In addition, it may be interesting to
evaluate such solvers on different (given) underlying graph topologies.
Finally, we focused on three gradual semantics in this paper. However, many
other weighted semantics have been proposed (e.g., [29, 30, 31, 32, 25]), and
extending the current work to these, and in particular, to probabilistic
semantics [33, 34] would be interesting.

We can consider another inverse problem, namely the computation of semantics
for a given weighted argumentation framework and set of final acceptability
degrees or preferences over arguments. We note in passing that this problem is
trivial to solve in polynomial time, as one simpy needs to check for
consistency between the inputs (weighted argumentation framework) and outputs
(final acceptability degrees or preferences) for each semantics.

Turning to related work, researchers have examined the notion of _argument
realisability_ in abstract argumentation frameworks [35], seeking to identify
an attack relation that yields a specific labelling or extension. Recent work
by Mumford et al. [36] has shown that — for complete semantics and IN/OUT
labellings — the problem is NP-complete, whereas it can be solved in
polynomial time if UNDEC labellings are also allowed. The work of Skiba et al.
[37] focuses on whether — for a given ranking and ranking-based semantics — we
can find an unweighted argumentation framework such that the selected ranking-
based semantics induces the ranking when applied to the argumentation
framework. They show that the above problem is true for a number of ranking-
based semantics, including burden-based and discussion-based semantics [38],
the simple product semantics on social abstract frameworks [25, 31], and the
probabilistic graded semantics [39, 40]. Another related area to the current
work is _argument synthesis_ [41], where the attack relation must satisfy some
positive and negative constraints, but where the problem is not fully
constrained. There are still several open questions regarding the time
complexity of these types of problems, even for the case of abstract
argumentation semantics [36].

More generally, our work can be seen as a type of inverse argumentation
problem. [13, 26] has examined one such inverse problem in the context of the
gradual semantics, seeking to identify a set of initial weights given a
semantics, a set of arguments, attacks and final acceptability degrees. In the
context of abstract argumentation, such inverse problems have examined
inferring preferences from justified arguments [42, 18], and has applications
in the context of belief revision [43].

The current paper focuses on the complexity of the underlying decision problem
and inferring attacks given the semantics, initial weights, and final
acceptability degrees. This — in a sense — is unrealistic, and limits the
applications of the current work. In most uses of gradual semantics, one
considers the preferences obtained from final acceptability degrees rather
than the final acceptability degrees themselves, as the latter are not
(normally) exposed within an application. Thus, as future work, we intend to
consider the problem of inferring attacks from a semantics, initial weights,
and preferences over arguments. We believe that the complexity of this problem
for a given semantics will be similar to that obtained in the current work.
Given this more general problem one could — for example — determine whether an
agent is rational given the initial weights they assign to a set of arguments,
a semantics, and a resultant preference ordering over the arguments. Other
applications, as discussed above, include opponent modelling [19] in the
context of dialogue and preference elicitation.

##  6 Conclusions

We have considered the problem of inferring an attack relation given a gradual
semantics and all initial weights and final acceptability degrees for an
argumentation framework. We have shown that for the weighted max-based
semantics, this problem can be solved in linear time, but that the obtained
solution is (typically) not unique. For the h-categoriser and cardinality
semantics — where solutions have no redundancies — the problem becomes NP-
complete. Our proofs are based on a reduction to variants of the subset-sum
problem, and efficient solvers for this problem can be applied to our work,
facilitating its application in domains such as opponent modelling. Finally,
we have focused on the complete problem, and there are exciting avenues for
future research dealing with its partial form.

## References

  * [1] Phan Minh Dung.  On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games.  Artif. Intell., 77(2):321–358, 1995.
  * [2] Sanjay Modgil and Henry Prakken.  A general account of argumentation with preferences.  Artif. Intell., 195:361–397, 2013.
  * [3] Souhila Kaci.  Working with Preferences: Less Is More.  Cognitive Technologies. Springer, 2011.
  * [4] Bruno Yun, Pierre Bisquert, Patrice Buche, and Madalina Croitoru.  Arguing About End-of-Life of Packagings: Preferences to the Rescue.  In Metadata and Semantics Research - 10th International Conference, MTSR 2016, Göttingen, Germany, November 22-25, 2016, Proceedings, pages 119–131, 2016.
  * [5] Leila Amgoud and Srdjan Vesic.  Two Roles of Preferences in Argumentation Frameworks.  In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Belfast, UK, June 29-July 1, 2011. Proceedings, pages 86–97, 2011.
  * [6] Leila Amgoud and Srdjan Vesic.  Rich preference-based argumentation frameworks.  Int. J. Approx. Reasoning, 55(2):585–606, 2014.
  * [7] Leila Amgoud, Claudette Cayrol, Marie-Christine Lagasquie-Schiex, and P. Livet.  On bipolarity in argumentation frameworks.  Int. J. Intell. Syst., 23(10):1062–1093, 2008.
  * [8] Leila Amgoud and Jonathan Ben-Naim.  Weighted bipolar argumentation graphs: Axioms and semantics.  In Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 5194–5198. ijcai.org, 2018.
  * [9] Claudette Cayrol and Marie-Christine Lagasquie-Schiex.  On the Acceptability of Arguments in Bipolar Argumentation Frameworks.  In Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 8th European Conference, ECSQARU 2005, Barcelona, Spain, July 6-8, 2005, Proceedings, pages 378–389, 2005.
  * [10] Till Mossakowski and Fabian Neuhaus.  Modular Semantics and Characteristics for Bipolar Weighted Argumentation Graphs.  CoRR, abs/1807.06685, 2018.
  * [11] Pietro Baroni, Martin Caminada, and Massimiliano Giacomin.  An introduction to argumentation semantics.  Knowledge Eng. Review, 26(4):365–410, 2011.
  * [12] Sylvie Coste-Marquis, Sébastien Konieczny, Pierre Marquis, and Mohand Akli Ouali.  Selecting Extensions in Weighted Argumentation Frameworks.  In Computational Models of Argument - Proceedings of COMMA 2012, Vienna, Austria, September 10-12, 2012, pages 342–349, 2012\.
  * [13] Nir Oren, Bruno Yun, Srdjan Vesic, and Murilo Baptista.  Inverse problems for gradual semantics.  In Proceedings of the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence, 2022.
  * [14] Benjamin Irwin, Antonio Rago, and Francesca Toni.  Argumentative forecasting.  In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’22, page 1636–1638, Richland, SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems.
  * [15] Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny, and Nicolas Maudet.  Combining Extension-Based Semantics and Ranking-Based Semantics for Abstract Argumentation.  In Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018., pages 118–127, 2018.
  * [16] Bruno Yun, Srdjan Vesic, Madalina Croitoru, and Pierre Bisquert.  Viewpoints using ranking-based argumentation semantics.  In Proceedings of the 7th International Conference on Computational Models of Argument, COMMA 2018, 11th - 14th September, 2018, Warsaw, Poland., 2018.
  * [17] Louise Dupuis de Tarlé, Elise Bonzon, and Nicolas Maudet.  Multiagent dynamics of gradual argumentation semantics.  In Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, and Matthew E. Taylor, editors, 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022, pages 363–371. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
  * [18] Quratul-ain Mahesar, Nir Oren, and Wamberto Weber Vasconcelos.  Preference elicitation in assumption-based argumentation.  In Takahiro Uchiya, Quan Bai, and Ivan Marsá-Maestre, editors, PRIMA 2020: Principles and Practice of Multi-Agent Systems - 23rd International Conference, Nagoya, Japan, November 18-20, 2020, Proceedings, volume 12568 of Lecture Notes in Computer Science, pages 199–214. Springer, 2020.
  * [19] Tjitze Rienstra, Matthias Thimm, and Nir Oren.  Opponent models with uncertainty for strategic argumentation.  In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pages 332–338, 2013.
  * [20] Sylwia Polberg and Anthony Hunter.  Empirical evaluation of abstract argumentation: Supporting the need for bipolar and probabilistic approaches.  International Journal of Approximate Reasoning, 93:487–543, 2018\.
  * [21] Leila Amgoud, Dragan Doder, and Srdjan Vesic.  Evaluation of argument strength in attack graphs: Foundations and semantics.  Artificial Intelligence, 302:103607, 2022.
  * [22] Antonio Rago, Francesca Toni, Marco Aurisicchio, and Pietro Baroni.  Discontinuity-Free Decision Support with Quantitative Argumentation Debates.  In KR 2016, pages 63–73, 2016.
  * [23] Salem Benferhat, Didier Dubois, and Henri Prade.  Argumentative inference in uncertain and inconsistent knowledge bases.  In David Heckerman and Abe Mamdani, editors, Uncertainty in Artificial Intelligence, pages 411–419. Morgan Kaufmann, 1993.
  * [24] Célia da Costa Pereira, Andrea Tettamanzi, and Serena Villata.  Changing one’s mind: Erase or rewind?  In Toby Walsh, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 164–171. IJCAI/AAAI, 2011.
  * [25] João Leite and João Martins.  Social Abstract Argumentation.  In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 2287–2292, 2011.
  * [26] Nir Oren, Bruno Yun, Assaf Libman, and Murilo S. Baptista.  Analytical solutions for the inverse problem within gradual semantics.  CoRR, abs/2203.01201, 2022.
  * [27] Marius Costandin.  A fptas for the subset sum problem with real numbers.  arXiv preprint arXiv:2110.09901, 2021.
  * [28] Matthias Thimm and Serena Villata.  The first international competition on computational models of argumentation: Results and analysis.  Artif. Intell., 252:267–294, 2017.
  * [29] Célia da Costa Pereira, Andrea Tettamanzi, and Serena Villata.  Changing one’s mind: Erase or rewind?  In Toby Walsh, editor, ICJAI, pages 164–171, 2011.
  * [30] Dov M. Gabbay and Odinaldo Rodrigues.  Equilibrium States in Numerical Argumentation Networks.  Logica Universalis, 9(4):411–473, 2015.
  * [31] Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny, and Nicolas Maudet.  A Comparative Study of Ranking-Based Semantics for Abstract Argumentation.  In Proc. AAAI, pages 914–920, 2016.
  * [32] Paul-Amaury Matt and Francesca Toni.  A Game-Theoretic Measure of Argument Strength for Abstract Argumentation.  In Logics in Artificial Intelligence, 11th European Conference, JELIA 2008, Dresden, Germany, September 28 - October 1, 2008. Proceedings, pages 285–297, 2008.
  * [33] Hengfei Li, Nir Oren, and Timothy J. Norman.  Probabilistic argumentation frameworks.  In TAFA, volume 7132 of Lecture Notes in Computer Science, pages 1–16, 2011.
  * [34] Anthony Hunter and Matthias Thimm.  Probabilistic reasoning with abstract argumentation frameworks.  J. Artif. Intell. Res., 59:565–611, 2017.
  * [35] T Linsbichler, J Puehrer, and H Strass.  " characterizing realizability in abstract argumentation".  In "Proceedings of the 16th International Workshop on Non-monotonic reasoning", 2020.
  * [36] Jack Mumford, Isabel Sassoon, Elizabeth Black, and Simon Parsons.  On the complexity of determining defeat relations consistent with abstract argumentation semantics.  In Proceedings of COMMA, 2022.
  * [37] Kenneth Skiba, Matthias Thimm, Tjitze Rienstra, Jesse Heyninck, and Gabriele Kern-Isberner.  Realisability of rankings-based semantics.  In Sarah Alice Gaggl, Jean-Guy Mailly, Matthias Thimm, and Johannes Peter Wallner, editors, Proceedings of the Fourth International Workshop on Systems and Algorithms for Formal Argumentation co-located with the 9th International Conference on Computational Models of Argument (COMMA 2022), Cardiff, Wales, United Kingdom, September 13, 2022, volume 3236 of CEUR Workshop Proceedings, pages 73–85. CEUR-WS.org, 2022.
  * [38] Leila Amgoud and Jonathan Ben-Naim.  Ranking-Based Semantics for Argumentation Frameworks.  In Proc. Scalable Uncertainty Management, pages 134–147, 2013\.
  * [39] Matthias Thimm, Federico Cerutti, and Tjitze Rienstra.  Probabilistic graded semantics.  In Sanjay Modgil, Katarzyna Budzynska, and John Lawrence, editors, Computational Models of Argument - Proceedings of COMMA 2018, Warsaw, Poland, 12-14 September 2018, volume 305 of Frontiers in Artificial Intelligence and Applications, pages 369–380. IOS Press, 2018.
  * [40] Hengfei Li, Nir Oren, and Timothy J. Norman.  Probabilistic argumentation frameworks.  In Sanjay Modgil, Nir Oren, and Francesca Toni, editors, Theorie and Applications of Formal Argumentation - First International Workshop, TAFA 2011. Barcelona, Spain, July 16-17, 2011, Revised Selected Papers, volume 7132 of Lecture Notes in Computer Science, pages 1–16. Springer, 2011.
  * [41] Andreas Niskanen, Johannes Wallner, and Matti Järvisalo.  Synthesizing argumentation frameworks from examples.  Journal of Artificial Intelligence Research, 66:503–554, 2019.
  * [42] Quratul-ain Mahesar, Nir Oren, and Wamberto Weber Vasconcelos.  Computing Preferences in Abstract Argumentation.  In PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference, Tokyo, Japan, October 29 \- November 2, 2018, Proceedings, pages 387–402, 2018.
  * [43] Ringo Baumann and Gerhard Brewka.  Agm meets abstract argumentation: Expansion and revision for dung frameworks.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.


# Ballistic graphene array for ultra-high pressure sensing

Abhinaba Sinha  Department of Electrical Engineering, Indian Institute of
Technpology Bombay, Powai, Mumbai-400076, India  Pankaj Priyadarshi  School of
Engineering, University of Warwick, Coventry- CV47AL, United Kingdom
Bhaskaran Muralidharan<EMAIL_ADDRESS>Department of Electrical Engineering,
Indian Institute of Technpology Bombay, Powai, Mumbai-400076, India

###### Abstract

Atomically thin two-dimensional materials such as graphene exhibit extremely
high-pressure sensitivity compared to the commercially used pressure sensors
due to their high surface-to-volume ratio and excellent mechanical properties.
The smaller piezoresistance of graphene across different transport regimes
limits its pressure sensitivity compared to other two-dimensional materials.
Using membrane theory and thin-film adhesivity model, we show miniaturization
as means to enhance the overall performance of graphene pressure sensors. Our
findings reveal that ballistic graphene can be configured to measure ultra-
high pressure ($\approx 10^{9}$ Pa) with many-fold higher sensitivity per unit
area than quasi-ballistic graphene, diffusive graphene, and thin layers of
transition metal dichalcogenides. Based on these findings, we propose an array
of ballistic graphene sensors with extremely high-pressure sensitivity and
ultra high-pressure range that will find applications in next-generation NEMS
pressure sensors. The performance parameters of the array sensors can be
further enhanced by reducing the size of graphene membranes and increasing the
number of sensors in the array. The methodology developed in this paper can be
used to explore similar applications using other two-dimensional materials.

##  I Introduction

The discovery of piezoresistance in silicon and germanium in 1954 laid the
foundation for silicon strain gauges Smith (1954). Following this development,
the first silicon diaphragm-based pressure sensor was commercially introduced
in 1958 Bryzek  _et al._ (1990). Further progress in silicon fabrication
processes such as anisotropic etching Kendall (1975); Bean (1978); Bassous
(1978), ion implantation Gandhi and Principles (1983), anodic bonding
Pomerantz (1968); Wallis and Pomerantz (1969), and micro-machining processes
Bryzek  _et al._ (1990) paved the way for a reduction in thickness of the
membranes and the sensor dimensions. The entire class of sensors that came
into being as a result of these developments is known as thin-film micro-
electro-mechanical (MEMS) pressure sensors.
Thin-film MEMS pressure sensors are extremely useful for pressure sensing due
to their high sensitivity and compact size Shih-Chin Gong and Chengkuo Lee
(2001a); Smith  _et al._ (2013). The mathematical expression for pressure
sensitivity (PS) of silicon obtained by Gong et al. Shih-Chin Gong and
Chengkuo Lee (2001a) predicts an increase in the PS with the reduction in
membrane thickness. Consequently, atomically thin 2-D materials are expected
to have very high PS and are considered as suitable replacements for
conventional membranes in pressure sensors. This fact was experimentally
confirmed by Smith et. al Smith  _et al._ (2013) and Wagner et. al Wagner  _et
al._ (2018) on graphene and $\mathrm{PtSe_{2}}$ respectively.
Usually, 2-D Dirac materials such as graphene have a lower gauge factor (GF)
than non-Dirac 2-D materials such as layered transition metal dichalcogenides
(TMDs), phosphorene, arsenene, and to name a few due to the presence of robust
Dirac cones Sinha  _et al._ (2019, 2020). Hence, non-Dirac 2-D materials have
higher PS than 2-D Dirac materials Zhang  _et al._ (2017); Nourbakhsh and
Asgari (2018); Manzeli  _et al._ (2015); Hosseini  _et al._ (2015); W.Zhang
_et al._ (2021); Wagner  _et al._ (2018); An  _et al._ (2019). Apart from PS,
the performance of a membrane pressure sensor is determined by its yield
pressure ($P_{yp}$, pressure at the yield point) Shih-Chin Gong and Chengkuo
Lee (2001a), and critical pressure ($P_{cr}$, the pressure required to
delaminate a membrane from the substrate) Koenig  _et al._ (2011). Amongst
different 2-D materials, graphene is considered a strong contender for next-
generation pressure sensors because of its high elastic limit (more than
$20\%$) Lee  _et al._ (2008), high adhesivity Koenig  _et al._ (2011), and
high impermeability Bunch  _et al._ (2008). Despite the excellent overall
properties of graphene, recent studies have shown many-fold higher PS of
$\mathrm{PtSe_{2}}$ than graphene Smith  _et al._ (2013); Wagner  _et al._
(2018) due to the presence of band gap in $\mathrm{PtSe_{2}}$ Wang  _et al._
(2015a).
In this paper, we intend to enhance the PS of graphene further and bring it at
par with that of the TMDs. We explore miniaturization as a means to enhance
the performance of graphene membranes for next-generation NEMS pressure
sensors. The rapid advancement in the state-of-the-art lithography techniques
has down-scaled MEMS systems to nanometer range (NEMS) Plummer (2009). The
membrane theory Zhao (2008); Timoshenko and Woinowsky-Krieger (1959) and thin-
film adhesivity model Gent and Lewandowski (1987); Liland  _et al._ (2019)
predict an increase in the magnitude of strain and critical pressure of the
membrane, respectively, with dimension reduction. This will lead to an overall
performance enhancement and reduction in the dimension of the graphene
pressure sensor.
In the subsequent sections, we develop a theoretical model to calculate the
pressure-induced strain within a membrane. Using it, we obtain the PS and
pressure range (PR) of graphene membranes in the ballistic, quasi-ballistic,
and diffusive regimes. The detailed derivations are given in the Appendix
sections.

##  II Theoretical Model

###  II.1 Simulation setup

The schematic diagram of the device setup meant to calculate the PS of
graphene is depicted in Fig. 1. We use a circular membrane of variable radius
$a$ on different substrates to calculate the PS of graphene in different
transport regimes, namely ballistic, quasi-ballistic and diffusive regimes.
The pressure difference (up to $10^{9}$ Pa) applied across the surfaces of the
membrane and the corresponding change in electrical resistance due to the
deflection are measured (refer to Fig. 1). The change in resistance with
pressure is used to calculate the PS.

Figure 1: (a) Schematic diagram for device setup: a circular graphene membrane
of radius ‘a’ on different substrates, used to calculate the pressure
sensitivity of graphene. (b) Schematic depicting the deflection of graphene
membrane due to an applied pressure across its surfaces.

###  II.2 Pressure sensitivity of graphene

Pressure sensitivity can be expressed as

$P.S.=GF\times\frac{\varepsilon}{P},$ (1)

where $GF$ is the gauge factor, $\varepsilon$ is the strain, and $P$ is the
pressure difference across the surface (refer to Appendix A). The PS depends
on GF and the ratio of strain and pressure. We measure the deflection of
membrane as a function of pressure using membrane theory Timoshenko and
Woinowsky-Krieger (1959); Zhao (2008) and obtain the strain in the membrane.
Using the values of strain as a function of pressure, we calculate the PS
using the value of GF of graphene in different transport regimes Sinha  _et
al._ (2019, 2020). Graphene has a very low GF across different transport
regimes. Thus, the PS of graphene can be increased by increasing the ratio of
$\frac{\varepsilon}{P}$. Since the elastic limit of graphene is very high Lee
_et al._ (2008), its adhesivity with the substrate plays a vital role in
defining the maximum PR of the graphene sensor.
In the subsequent sub-sections, we obtain the mathematical strain as a
function of pressure using the deflection of membrane as a function of
pressure. Furthermore, we obtain the critical pressure of graphene membranes
of different dimensions on various substrates to find the maximum pressure
range.

####  II.2.1 Deflection of membrane

The deflection of the membrane ($w$) in the z-direction can be approximated
(see Fig. 1) as

$w=w_{0}\bigg{(}1-\frac{r^{2}}{a^{2}}\bigg{)},$ (2)

where, $w_{0}$ is the deflection of the center of the membrane, r is the
radius of the circle formed in the deflected membrane whose center lies at the
coordinates (0, 0, w), and $a$ is the radius of the blister Zhao (2008) (see
Fig. 1). The value of $w_{0}$ can be calculated by applying the principle of
virtual displacement and relevant boundary conditions Zhao (2008); Timoshenko
and Woinowsky-Krieger (1959). Thus, the expression for $w_{0}$ is given by

$\displaystyle\frac{w_{0}}{a}=$
$\displaystyle\bigg{(}-\frac{\eta}{2}+\zeta\bigg{)}^{\frac{1}{3}}+\bigg{(}-\frac{\eta}{2}-\zeta\bigg{)}^{\frac{1}{3}},$
(3a) $\displaystyle\zeta=$
$\displaystyle\sqrt{\bigg{(}\frac{\xi}{3}\bigg{)}^{3}+\bigg{(}\frac{\eta}{2}\bigg{)}^{2}},$
(3b) $\displaystyle\xi=$
$\displaystyle\frac{4}{7-\gamma}\bigg{(}\frac{h}{a}\bigg{)}^{2},and$ (3c)
$\displaystyle\gamma=$
$\displaystyle\bigg{\\{}\frac{3(\nu-1)}{7-\nu}\bigg{\\}}\frac{Pa}{Eh},$ (3d)

where $\nu$, $h$, $P$, $E$ are respectively the Poisson’s ratio, thickness,
pressure, and Young’s modulus of the graphene membrane.

####  II.2.2 Strain along the direction of transport

Figure 2: Schematic depicting the methodology for average strain calculation
in a deflected membrane. The strain value is averaged over $n$ discrete paths.
The top and side views of a single path are sketched.

Figure 3: (a) Displacement of the center of membrane ($w_{0}$), and (b)
average strain as a function of pressure for different membrane sizes. (c)
Critical pressure of graphene sensors as a function of radius for different
substrates. (d) Bar plot illustrating the critical strain of graphene on
different substrates.

An applied pressure across the surface of a circular graphene membrane induces
bi-axial strain. In order to calculate PS from uni-axial strain GF, strain
along the direction of current flow is required. Sinha  _et al._ (2019, 2020).
Thus, we obtain a mathematical expression of strain along a specific direction
of the deflected membrane. The deflection along various parallel paths,
passing through the coordinate $(x_{i},0,0)$ for different values of $x_{i}$
is different (see Fig. 2). Thus, it is required to compute the average strain
of these paths. The detailed derivation of the expression for average strain
along a particular direction is given in Appendix B. The expression for strain
is given by

$\displaystyle\varepsilon_{i}$ $\displaystyle=\frac{L_{i}-L_{0}}{L_{0}},$ (4a)
$\displaystyle\varepsilon_{i}$
$\displaystyle=\frac{\sqrt{1+Y^{2}}}{2}-1+\frac{1}{2Y}log|Y+\sqrt{1+Y^{2}}|,$
(4b) $\displaystyle\varepsilon_{avg.}$
$\displaystyle=\frac{1}{N}\sum\limits_{i=1}^{N}\varepsilon_{i},$ (4c)

where $Y=Ay_{i}$, and $A=\frac{-2w_{0}}{a^{2}}$ and
$y_{i}=\sqrt{a^{2}-{x_{i}}^{2}}$ (see Appendix C for detail derivation).

Figure 4: (a)-(c) Pressure sensitivity per unit area as a function of pressure for membrane radii $100~{}nm$, $1~{}\mu m$, and $10~{}\mu m$ respectively. (d) Comparison of normalized pressure sensitivities of ballistic, quasi ballistic, and diffusive graphene sensors with commercially used materials. Table 1: Comparison between the values of $w_{0}$ obtained in this work and by Bunch et. al Bunch  _et al._ (2008) at different pressure. $\bm{P~{}(MPa)}$ |  $\bm{w_{0}(nm)}$ (This work) |  $\bm{w_{0}(nm)}$ Bunch  _et al._ (2008)
---|---|---
0.145 | 147 | 130
0.41 | 207 | 220
0.81 | 260 | 280

####  II.2.3 Adhesivity of graphene

Graphene is highly adhesive due to its ability to conform to the topography of
the substrates Koenig  _et al._ (2011). Its high elastic limit Lee  _et al._
(2008) along with the high adhesivity Koenig  _et al._ (2011) and
impermeability Bunch  _et al._ (2008) is useful for high-pressure sensing. The
maximum PR of graphene depends on its yield-pressure Shih-Chin Gong and
Chengkuo Lee (2001b) as well as critical pressure Koenig  _et al._ (2011).
The PS can be evaluated using Eq. 1, once the ratio of average strain and
pressure is obtained from Eq. 4. The critical pressure of a membrane whose
thickness is significantly less than its diameter is given by

$P_{cr}=\frac{(17.4EhG^{3}_{a})^{\frac{1}{4}}}{a},$ (5)

where $P_{cr}$ is the critical pressure, $E$ is Young’s modulus, $h$ is the
thickness of the membrane, $G_{a}$ is the adhesivity, and $a$ is the radius of
the circular membrane Gent and Lewandowski (1987). Using Eq. (5), we obtain
the critical pressure of graphene on various substrates. This model accurately
predicts the critical pressure of graphene obtained by Koenig et al. Koenig
_et al._ (2011). The critical pressure obtained experimentally by Koenig et
al. for a $2.5~{}\mu m$ radius graphene membrane on $SiO_{2}$ is 1.14 MPa
whereas, the critical pressure predicted by Eq. (5) is 1.4 MPa which is pretty
close to the experimentally obtained.

##  III Results and Discussion

Figure 5: (a) $w_{0}/a$ vs pressure ($P$), and (b) $w_{0}/a^{2}$ vs pressure
($P$) at different values of membrane radius ‘$a$’. The value of $w_{0}/a$
decreases as the radius ‘$a$’ decreases while, $w_{0}/a^{2}$ increases as the
radius ‘$a$’ decreases. Plot (a) implies reduction in PS with decrease in
radius ‘$a$’, whereas plot (b) implies an increase in the PS per unit area
with decrease in radius ‘$a$’.

Figure 6: Schematics illustrating (a) a graphene pressure sensor of radius
$10\mu m$ formed from a square sheet of side $20~{}\mu m$, (b) an array of
graphene pressure sensors of radius $100~{}nm$ or $1~{}\mu m$ formed from a
square sheet of side $2~{}\mu m$ or $20~{}\mu m$ respectively, and (c) an
array of graphene pressure sensors of radius $100~{}nm$ formed from a square
graphene sheet of side $20~{}\mu m$. The ratio of pressure sensitivities of:
(d) sensors in sub-figures (b) and (a), (e) sensors of sub-figures (b) and
(c), and (f) sensors in sub-figures (c) and (a).

Figure 7: (a) Circuit diagram of a Multi-channel Wheatstone bridge
configuration for graphene array pressure sensors. Output voltage ($V_{out}$)
measured using $n$-channel Wheatstone bridge shown in (a) for different number
of pressure sensors ($n$) having radius (b) $10\mu m$, (c) $1\mu m$ , and (d)
$100~{}nm$ in array configuration. The output voltage and pressure range
(represented by yellow shaded region) increase by reducing the size of sensors
and increasing the number of sensors in the array, keeping the size of the
original graphene sheet intact.

The performance of a graphene pressure sensor depends on the membrane material
and the substrate. The graphene membrane determines the yield pressure
(pressure at the yield point), whereas the adhesivity on substrates determines
the critical pressure (minimum pressure required to delaminate graphene from
the substrate). Because of the high elastic limit (more than $20\%$), yield
pressure is much larger than the critical pressure in a graphene pressure
sensor. Thus, the PR of a graphene sensor depends on its interaction with the
substrate.
Figure 3 shows an increase in the value of $w_{0}$ with an increase in the
membrane radius ‘$a$’, which is evident from Eq. (3). Further, in Fig. 3, we
observe an increase in the yield pressure with a reduction in the membrane
radius. It is because the strain in a deflected membrane is proportional to
$\frac{w^{2}_{0}}{a^{2}}$ at a constant pressure Timoshenko and Woinowsky-
Krieger (1959); Zhao (2008) (see D) and the value of $\frac{w^{2}_{0}}{a^{2}}$
decreases as radius ‘$a$’ decreases (see Fig. 5). Since the value of yield
strain of graphene is independent of its dimension. So, the yield point is
reached at a higher pressure when its radius is smaller. The yield pressures
of $10~{}\mu m$, $1~{}\mu m$, and $100~{}nm$ are of the order of $10^{8}$ Pa,
$10^{9}$ Pa, and $10^{10}$ Pa, respectively.
Further, we obtain the critical pressure of graphene from Eq. 5, which is
inversely proportional to the radius ‘$a$’. Consequently, we witness an
increase in the critical pressure with the reduction in radius (see Fig. 3).
Figure 3 shows the variation of critical pressure as a function of membrane
size and substrate. The figure concludes that critical pressure increases 100
times when its radius reduces from $10~{}\mu m$ to $100~{}nm$. Apart from the
radius, the critical pressure of graphene strongly depends on the substrate.
In general, graphene is more adhesive to metal substrates such as nickel,
gold, and copper than amorphous insulators such as $SiO_{2}$ Megra and Suk
(2019). Nickel has the highest adhesivity reported so far because of stronger
graphene-metal interaction and better lattice match Gamo  _et al._ (1997).
From Figs. 3 and 3, we infer that because of the large yield pressure of
graphene, the critical pressure determines the upper limit of the PR. The
critical strains of graphene on various substrates are shown in Fig. 3. Out of
them, graphene has the highest critical strain of $\approx~{}10\%$ with nickel
which is within the linear elastic limit of graphene Pereira  _et al._ (2009).
Using Eq. 4, we obtain the PS of ballistic, quasi-ballistic, and diffusive
graphene from the values of $\frac{\varepsilon}{P}$ and GF at different
transport regimes. Figure 4 plots the PS of ballistic, quasi-ballistic, and
diffusive graphene and compares their sensitivity with various commercially
used membranes. From these plots, we find that ballistic graphene
($a=100~{}nm$) has a very high PS per unit area of nearly $2.5\times
10^{4}~{}Pa^{-1}m^{-2}$. It is approximately twenty-five times more sensitive
than diffusive graphene ($10~{}\mu m$) and five times more sensitive than
quasi-ballistic graphene. The miniaturization of graphene increases its PS per
unit area and significantly enhances the PR. The PS per unit area is
proportional to $\frac{w^{2}_{0}}{a^{4}}$ (see Appendix D). The value of
$\frac{w^{2}_{0}}{a^{4}}$ increases as radius ‘$a$’ reduces (see Fig. 5). The
maximum pressure that can be sensed using ballistic, quasi-ballistic, and
diffusive graphene is of the order of $10^{9}$ Pa, $10^{8}$ Pa, and $10^{7}$
Pa respectively.
Despite a very low GF Sinha  _et al._ (2019, 2020); Smith  _et al._ (2013,
2016), graphene has a significantly higher PS per unit area than silicon
($10^{3}-10^{4}$ times) and GaAs ($10^{5}$ times) pressure sensors due to its
high surface-to-volume ratio Smith  _et al._ (2013). Hence, other atomically
thin 2-D materials are also expected to have a high-PS like graphene or even
more Wagner  _et al._ (2018). Amongst them, TMDs are considered to be the
leading contender for replacing graphene due to their high GF (see Table 2).
Nevertheless, the mechanical properties of graphene are unparalleled, and no
other thin-film material could compete with it so far. The excellent
adhesivity Bunch  _et al._ (2008) and mechanical properties Lee  _et al._
(2008) of graphene give rise to its high PR. The value of PS per unit area of
a 2-D sheet of $\mathrm{PtSe_{2}}$, is $10^{4}~{}Pa^{-1}m^{-2}$ Wagner  _et
al._ (2018). Figure 4 shows that the PS of graphene in the sub-micron length
scale is comparable to that of the $\mathrm{PtSe_{2}}$, despite the latter
having a high GF of -85 Wagner  _et al._ (2018). Thus, using miniaturization
of graphene, we can design pressure sensors that have a very high PR and high
PS like the TMDs.
The higher value of PS per unit area of ballistic graphene does not guarantee
higher PS than quasi-ballistic and diffusive graphene due to its smaller
surface area. We propose a novel way to overcome this limitation by forming a
large array of ballistic graphene nano-sensors from a graphene sheet instead
of using a single large-sized graphene sensor. By doing so, we effectively
increase the overall PS and PR of the graphene sensors. Figures 4, 4 and 4
show the formation of a single pressure sensor of radius $10~{}\mu m$ from a
$20~{}\mu m$ edge square graphene sheet, formation of an array of pressure
sensors of radius $100~{}nm$ and $1~{}\mu m$ from a $2~{}\mu m$ and $20~{}\mu
m$ square graphene sheet respectively, and formation of an array of pressure
sensors of radius $100~{}nm$ from a $20~{}\mu m$ square graphene sheet. The
relative PS of array sensors and a single pressure sensor formed from the same
graphene sheet is shown in Figs. 6, 6 and 6. The relative PS is highest for
$100~{}nm$ radius pressure sensor formed from a $20~{}\mu m$ square graphene
sheet and is lowest for $100~{}nm$ radius pressure array formed from a
$1~{}\mu m$ square graphene sheet. Hence, we conclude that the smaller the
radius of pressure sensors and the larger the size of the graphene sheet, the
more is the PS of the system. The advantage of such a system is that a high-PS
and high-PR are simultaneously obtained. Based on these findings, we propose
an array sensor of radius $100~{}nm$ formed from a large graphene sheet
connected to a multi-channel Wheatstone bridge.
In a $n$-channel Wheatstone bridge, each channel has one pressure sensor
(represented by P) and a reference piezoresistor (represented by
$\mathrm{P^{{}^{\prime}}}$) (see Fig. 7). The combination of $n$ channels is
identical to $n$ pressure sensors and reference piezoresistor in series in an
array configuration. The resultant differential output signal from each
channel of the Wheatstone bridge is added to obtain a larger voltage output
($V_{out}$). The use of array sensors using graphene is highly advantageous.
The voltage output of a single graphene pressure sensor of radius $20~{}\mu m$
is shown in Fig. 7, whereas in Fig. 7 array of graphene membranes of radius
$1~{}\mu m$ are shown for $n$=1 and 100 and in Fig. 7 array of graphene
membranes of radius $100~{}nm$ are shown for $n$=1, 100 and 10000. These
figures conclude that the output voltage of smaller-sized array sensors made
from a larger sheet when used in the multi-channel Wheatstone bridge
configuration is many folds more sensitive than a single pressure sensor made
from an identical graphene sheet. We notice a sharp increase in its PR (yellow
shaded region) also when multiple smaller sensors are used instead of a single
large graphene sensor is used.
Piezoresistive pressure sensor transforms pressure waves (sound waves are
longitudinal pressure waves) into electrical signals, which is very similar to
how a microphone works. Since graphene microphones have the advantage of being
resonance-free in the acoustic range Wittmann  _et al._ (2019), thus,
ballistic graphene array nano-sensors can be instrumental in designing highly
sensitive microphones with high pitch and can eventually be useful in modern
smart phones.
Apart from this, the methodology used for analyzing ballistic graphene
pressure sensors in this paper can be used to explore similar applications in
other 2-D materials. Amongst 2-D materials, Dirac materials have lower GF than
TMDs due to the robust Dirac cones Hosseini  _et al._ (2015). Hence, it is
more likely that nanoscale TMD sheets will have a larger PS than graphene,
despite a smaller PR due to lower elastic limit of TMDs than graphene (see
Table 2).

Table 2: Thickness, Poisson’s ratio, Young’s modulus, Elastic limit, and Gauge factor of some common 2-D materials $\bm{Materials}$ | $\bm{h~{}(nm)}$ |  $\bm{\nu}$ | $\bm{E~{}(N/m)}$ | $\bm{\varepsilon~{}(\%)}$ | $\bm{GF}$
---|---|---|---|---|---
$\bm{Graphene}$ | 0.335 Novoselov  _et al._ (2004); Castro Neto  _et al._ (2009) | 0.14 Ribeiro  _et al._ (2009) | 335 John and Merlin (2016) |  $>20$ Lee  _et al._ (2008) | 0.3-10.3 Sinha  _et al._ (2019, 2020); Smith  _et al._ (2013)
$\bm{Silicene}$ | 0.313 Peng  _et al._ (2013) | 0.31 Qin  _et al._ (2014) | 61.33 John and Merlin (2016) | 5 Peng  _et al._ (2013) | -1.4
$\bm{Phosphorene}$ | 0.9 Liu  _et al._ (2014a) | 0.70(zz),0.18(ac) Wang  _et al._ (2015b) | 92 (zz),23 (ac) Wei and Peng (2014); Wang  _et al._ (2015b) | 2 Liu  _et al._ (2019) | 120 Zhang  _et al._ (2017); Nourbakhsh and Asgari (2018)
$\bm{MoS_{2}}$ | 0.65 Li and Zhu (2015) | 0.25 Kang  _et al._ (2015) | 175.5 Bertolazzi  _et al._ (2011) | 3 Peng and De (2013) | -148 Manzeli  _et al._ (2015)
$\bm{MoSe_{2}}$ | 0.8 Lu  _et al._ (2014) | 0.25 Yoo  _et al._ (2018) | 80 Wang  _et al._ (2019) | 2.5 Yang  _et al._ (2017) | 1700 Hosseini  _et al._ (2015)
$\bm{WS_{2}}$ | 0.9 Park  _et al._ (2017) | 0.23 Yoo  _et al._ (2018) | 170 Liu  _et al._ (2014b) | 2 Deng  _et al._ (2018a) | 70 W.Zhang  _et al._ (2021)
$\bm{WSe_{2}}$ | 1.5 Chen  _et al._ (2018) | 0.21 Yoo  _et al._ (2018) | 132.8 Zeng  _et al._ (2015) | 2.5 Ding  _et al._ (2019) | 3000 Hosseini  _et al._ (2015)
$\bm{PtSe_{2}}$ | 0.507 Kliche (1985) | 0.25 Du  _et al._ (2018) | 58.76 Deng  _et al._ (2018b) | 2 Du  _et al._ (2018) | -85 Wagner  _et al._ (2018)
$\bm{ReSe_{2}}$ | 0.66 Yang  _et al._ (2014) | 0.223 Wang  _et al._ (2017) | 92.4 Wang  _et al._ (2017) | 3 An  _et al._ (2019) | 50 An  _et al._ (2019),-60 An  _et al._ (2019)

##  IV Conclusion

Motivated by the recent findings that showed the high-pressure sensitivity of
atomically thin materials such as graphene, we explored the pressure
sensitivity of miniaturized graphene membranes on various substrates using the
membrane theory and thin-film adhesivity model. We used these findings on
graphene membranes of different dimensions on various substrates and found a
$10^{3}$ fold enhancement in the normalized pressure sensitivity per unit area
of ballistic graphene compared to commercial silicon pressure sensors. Apart
from pressure sensitivity, we showed that ballistic graphene could sense
ultra-high pressure of the order of $10^{9}$ Pa. Moreover, we also found that
ballistic graphene is 2-3 times more sensitive than TMD, such as
$\mathrm{PtSe_{2}}$, despite the latter having a much higher gauge factor
compared to graphene. Finally, this paper concludes that a ballistic graphene
pressure sensor is a perfect blend of high-pressure sensitivity and ultra-high
pressure range. Based on these results, we proposed ballistic graphene array
sensors as next-generation NEMS pressure sensors for ultra-high pressure
sensing.

###### Acknowledgements.

The Research and Development work undertaken in the project under the
Visvesvaraya Ph.D. Scheme of Ministry of Electronics and Information
Technology, Government of India, is implemented by Digital India Corporation
(formerly Media Lab Asia). This work was also supported by the Science and
Engineering Research Board (SERB), Government of India, Grant No.
CRG/2021/003102 and Grant No. STR/2019/000030.

##  Appendix A Expression for pressure sensitivity

Pressure sensitivity is expressed as

$PS=\frac{\Delta R/R}{P},$ (6)

where $\Delta R$ is the change in resistance due to pressure $P$ and $R_{0}$
is the resistance of membrane at zero strain. The right hand side of Eq. 6 can
be written as $\frac{\Delta R}{\varepsilon R}\times\frac{\varepsilon}{P}$. The
quantitiy $\varepsilon$ is the strain generated in the membrane due to
pressure ($P$) and $\frac{\Delta R}{\varepsilon R}$ is the gauge factor (GF).
Thus, Eq. (6) simplifies into

$PS=GF\times\frac{\varepsilon}{P}$ (7)

##  Appendix B Deflection of membrane

The pressure difference across the top and bottom surfaces causes the membrane
to deflect (see Fig. 1). The large scale deflection of a membrane is
approximated by the expression

$w=w_{0}\bigg{(}1-\frac{r^{2}}{a^{2}}\bigg{)}.$ (8)

The radial displacement (u) can be approximately written as

$u=r(a-r)(c_{1}+rc_{2}),$ (9)

where $c_{1}$ and $c_{2}$ are constant.
The value of $w_{0}$ can be easily computed using the principle of virtual
displacement. According to this principle, change in mechanical energy is
equal to work done by the pressure to deflect the membrane Timoshenko and
Woinowsky-Krieger (1959). The mechanical energy of a membrane includes strain
energy and bending energy. On solving the value of $w_{0}$ using this
principle, we obtain an analytical expression of $w_{0}$ which is a function
of applied pressure, thickness, and radius of the membrane Zhao (2008);
Timoshenko and Woinowsky-Krieger (1959).
The value of strain energy of a circular membrane is given by

$\displaystyle V_{s}=\pi K\int\limits_{0}^{a}\big{(}\varepsilon_{r}^{2}+$
$\displaystyle\varepsilon_{\theta}^{2}+2\nu\varepsilon_{r}+\varepsilon_{\theta}\big{)}rdr,$
(10a) $\displaystyle K=$ $\displaystyle\frac{Eh}{1-\nu^{2}},$ (10b)
$\displaystyle\varepsilon_{r}=$
$\displaystyle\frac{du}{dr}+\frac{1}{2}\bigg{(}\frac{dw}{dr}\bigg{)}^{2},and$
(10c) $\displaystyle\varepsilon_{\theta}=$ $\displaystyle\frac{u}{r}.$ (10d)

On simplifying the above equations, we obtain the strain energy as

$\begin{split}V_{s}=&\frac{\pi
Eh}{1-{\nu}^{2}}\Bigg{[}\frac{1}{4}c_{1}^{2}a^{4}+\frac{3}{10}c_{1}c_{2}a^{5}-\frac{1}{5}(3-\nu)c_{1}aw_{0}^{2}\\\
&+\frac{7}{60}c_{2}^{2}a^{6}-\frac{2}{15}(3-\nu)c_{2}a^{2}w_{0}^{2}+\frac{2}{3}\frac{w_{0}^{4}}{a^{2}}\Bigg{]}\end{split}$
(11)

The bending strain energy of a membrane is given by Timoshenko and Woinowsky-
Krieger (1959)

$V_{b}=4\pi D(1+\nu)\bigg{(}\frac{w_{0}}{a}\bigg{)}^{2},$ (12)

where $D=\frac{Eh^{3}}{12(1-\nu^{2})}$ is the bending rigidity. The work done
by the pressure while deflecting the circular membrane is given by Zhao (2008)

$W=\frac{\pi a^{2}P}{2}w_{0}$ (13)

In equilibrium, the value of $V_{s}$ is minimum with respect to $c_{1}$ and
$c_{2}$. Using these conditions along with the principle of virtual
displacement Timoshenko and Woinowsky-Krieger (1959), we obtain the value of
$w_{0}$. The conditions are

$\displaystyle\frac{dV_{s}}{dc_{1}}=\frac{dV_{s}}{dc_{2}}$ $\displaystyle=0,$
(14a) $\displaystyle\frac{d(V_{s}+V_{b})}{dw_{0}}\delta w_{0}$
$\displaystyle=\frac{dW}{dw_{0}}\delta w_{0}.$ (14b)

On solving Eqs. (14), we obtain a cubic equation in terms of $w_{0}$ is
obtained which is given by Zhao (2008)

$w_{0}^{3}+\frac{4h^{2}}{(7-\nu)}w_{0}-\frac{3(1-\nu)Pa^{4}}{Eh}=0.$ (15)

Solving Eq. (15) using the Cardan’s Formula yields the Eq. (2).

##  Appendix C Strain along the direction of transport

The strain ($\varepsilon$) along a particular direction of transport is
different at different portions of the circular membrane, as shown in Fig. 2.
Thus, we have to calculate the average strain in the membrane due to applied
pressure. We divide the circular basement of the deflected membrane into a
large number of parallel chord paths along the direction of transport. The
strain in the geodesic arcs of the deflected membrane along these chord paths
are given by the difference in the length of the geodesic arc and the length
of the corresponding chords.
The length of the chord in an unstrained membrane passing through $(x_{i},0)$
is equal to $L_{0}=\sqrt{a^{2}-{x_{i}}^{2}}$. The length of the line passing
through the deflected surface is given by

$L_{i}=\int\limits_{0}^{\sqrt{a^{2}-x_{i}^{2}}}\sqrt{1+{\bigg{(}\frac{dw}{dy}\bigg{)}^{2}}}dy.$
(16)

The value of strain $\varepsilon_{i}$ can be written as

$\varepsilon_{i}=\frac{L_{i}-L_{0}}{L_{0}}.$ (17)

On simplification of Eq. C1 using Eq. B1, we obtain

$L_{i}=\frac{Y\sqrt{1+Y^{2}}}{2A}+\frac{1}{2A}log|Y+\sqrt{1+Y^{2}}|,$ (18)

where $Y=-\frac{-2w_{0}\sqrt{a^{2}-{x_{i}}^{2}}}{a^{2}}$ and
$A=\frac{-2w_{0}}{a^{2}}$. Further, using Eqs. (17) and (18), we obtain the
strain along the direction of transport.

##  Appendix D Pressure sensitivity per unit area of graphene membrane

The PS of a graphene membrane is given by Eq. (1). The GF of graphene is very
small across different length scales due to the presence of robust Dirac cones
Sinha  _et al._ (2019, 2020). According to Eq. (1), PS depends on the
magnitude of strain at a particular pressure. The radial ($\varepsilon_{r}$)
and tangential strains ($\varepsilon_{\theta}$) are expressed as

$\displaystyle\varepsilon_{r}$
$\displaystyle=\frac{3-\nu}{4}\bigg{(}\frac{w_{0}}{a}\bigg{)}^{2}\bigg{[}1-\frac{1-3\nu}{3-\nu}\bigg{(}\frac{r}{a}\bigg{)}^{2}\bigg{]},and$
(19a) $\displaystyle\varepsilon_{r}$
$\displaystyle=\frac{3-\nu}{4}\bigg{(}\frac{w_{0}}{a}\bigg{)}^{2}\bigg{[}1-\bigg{(}\frac{r}{a}\bigg{)}^{2}\bigg{]}$
(19b)

respectively Zhao (2008), where $\nu$ is the Poisson’s ratio. At any point in
the deflected membrane, strain components are directly proportional to
$\frac{w^{2}_{0}}{a^{2}}$. Thus, PS is directly proportional to
$\frac{w^{2}_{0}}{a^{2}}$, and PS per unit area is directly proportional to
$\frac{w^{2}_{0}}{a^{4}}$.

## References

  * Smith (1954) C. S. Smith, Phys. Rev. 94, 42 (1954).
  * Bryzek  _et al._ (1990) J. Bryzek, K. Petersen, J. Mallon, L. Christel, and F. Pourahmadi, Nova Sensor (1990).
  * Kendall (1975) D. L. Kendall, Applied Physics Letters 26, 195 (1975).
  * Bean (1978) K. E. Bean, IEEE Transactions on electron devices 25, 1185 (1978).
  * Bassous (1978) E. Bassous, IEEE Transactions on electron devices 25, 1178 (1978).
  * Gandhi and Principles (1983) S. K. Gandhi and V. F. Principles, “Silicon and gallium arsenide,” (1983).
  * Pomerantz (1968) D. I. Pomerantz, “Anodic bonding,” (1968), uS Patent 3,397,278.
  * Wallis and Pomerantz (1969) G. Wallis and D. I. Pomerantz, Journal of applied physics 40, 3946 (1969).
  * Shih-Chin Gong and Chengkuo Lee (2001a) Shih-Chin Gong and Chengkuo Lee, IEEE Sensors Journal 1, 340 (2001a).
  * Smith  _et al._ (2013) A. Smith, F. Niklaus, A. Paussa, S. Vaziri, A. C. Fischer, M. Sterner, F. Forsberg, A. Delin, D. Esseni, P. Palestri, _et al._ , Nano letters 13, 3237 (2013).
  * Wagner  _et al._ (2018) S. Wagner, C. Yim, N. McEvoy, S. Kataria, V. Yokaribas, A. Kuc, S. Pindl, C.-P. Fritzen, T. Heine, G. S. Duesberg, and M. C. Lemme, Nano Letters 18, 3738 (2018).
  * Sinha  _et al._ (2019) A. Sinha, A. Sharma, A. Tulapurkar, V. R. Rao, and B. Muralidharan, Phys. Rev. Materials 3, 124005 (2019).
  * Sinha  _et al._ (2020) A. Sinha, A. Sharma, P. Priyadarshi, A. Tulapurkar, and B. Muralidharan, Phys. Rev. Research 2, 043041 (2020).
  * Zhang  _et al._ (2017) Z. Zhang, L. Li, J. Horng, N. Z. Wang, F. Yang, Y. Yu, Y. Zhang, G. Chen, K. Watanabe, T. Taniguchi, X. H. Chen, F. Wang, and Y. Zhang, Nano Letters 17, 6097 (2017).
  * Nourbakhsh and Asgari (2018) Z. Nourbakhsh and R. Asgari, Phys. Rev. B 98, 125427 (2018).
  * Manzeli  _et al._ (2015) S. Manzeli, A. Allain, A. Ghadimi, and A. Kis, Nano Letters 15, 5330 (2015).
  * Hosseini  _et al._ (2015) M. Hosseini, M. Elahi, M. Pourfath, and D. Esseni, Applied Physics Letters 107, 253503 (2015).
  * W.Zhang  _et al._ (2021) W.Zhang, R. Frisenda, Q. Zhao, F. Carrascoso, A. Al-Enizi, A. Nafady, and A. Castellanos-Gomez, Preprints (2021).
  * An  _et al._ (2019) C. An, Z. Xu, W. Shen, R. Zhang, Z. Sun, S. Tang, Y.-F. Xiao, D. Zhang, D. Sun, X. Hu, C. Hu, L. Yang, and J. Liu, ACS Nano 13, 3310 (2019).
  * Koenig  _et al._ (2011) S. P. Koenig, N. G. Boddeti, M. L. Dunn, and J. S. Bunch, Nature nanotechnology 6, 543 (2011).
  * Lee  _et al._ (2008) C. Lee, X. Wei, J. W. Kysar, and J. Hone, Science 321, 385 (2008).
  * Bunch  _et al._ (2008) J. S. Bunch, S. S. Verbridge, J. S. Alden, A. M. van der Zande, J. M. Parpia, H. G. Craighead, and P. L. McEuen, Nano Letters 8, 2458 (2008).
  * Wang  _et al._ (2015a) Y. Wang, L. Li, W. Yao, S. Song, J. T. Sun, J. Pan, X. Ren, C. Li, E. Okunishi, Y.-Q. Wang, E. Wang, Y. Shao, Y. Y. Zhang, H.-t. Yang, E. F. Schwier, H. Iwasawa, K. Shimada, M. Taniguchi, Z. Cheng, S. Zhou, S. Du, S. J. Pennycook, S. T. Pantelides, and H.-J. Gao, Nano Letters 15, 4013 (2015a).
  * Plummer (2009) J. D. Plummer,  _Silicon VLSI technology: fundamentals, practice and modeling_ (Pearson Education India, 2009).
  * Zhao (2008) F. Zhao, in  _Modeling, Signal Processing, and Control for Smart Structures 2008_, Vol. 6926, edited by D. K. Lindner, International Society for Optics and Photonics (SPIE, 2008) pp. 232 – 243\.
  * Timoshenko and Woinowsky-Krieger (1959) S. Timoshenko and S. Woinowsky-Krieger,  _Theory of plates and shells_ (McGraw Hill, 1959).
  * Gent and Lewandowski (1987) A. Gent and L. Lewandowski, Journal of applied polymer science 33, 1567 (1987).
  * Liland  _et al._ (2019) K. B. Liland, H. Faremo, and K.-M. Furuheim, in  _Proceedings of the Nordic Insulation Symposium_ , 26 (2019) pp. 108–112.
  * Shih-Chin Gong and Chengkuo Lee (2001b) Shih-Chin Gong and Chengkuo Lee, IEEE Sensors Journal 1, 340 (2001b).
  * Megra and Suk (2019) Y. T. Megra and J. W. Suk, Journal of Physics D: Applied Physics 52, 364002 (2019).
  * Gamo  _et al._ (1997) Y. Gamo, A. Nagashima, M. Wakabayashi, M. Terai, and C. Oshima, Surface Science 374, 61 (1997).
  * Pereira  _et al._ (2009) V. M. Pereira, A. H. Castro Neto, and N. M. R. Peres, Phys. Rev. B 80, 045401 (2009).
  * Smith  _et al._ (2016) A. D. Smith, F. Niklaus, A. Paussa, S. Schröder, A. C. Fischer, M. Sterner, S. Wagner, S. Vaziri, F. Forsberg, D. Esseni, M. Östling, and M. C. Lemme, ACS Nano 10, 9879 (2016).
  * Wittmann  _et al._ (2019) S. Wittmann, C. Glacer, S. Wagner, S. Pindl, and M. C. Lemme, ACS Applied Nano Materials 2, 5079 (2019).
  * Novoselov  _et al._ (2004) K. S. Novoselov, A. K. Geim, S. V. Morozov, D. Jiang, Y. Zhang, S. V. Dubonos, I. V. Grigorieva, and A. A. Firsov, Science 306, 666 (2004).
  * Castro Neto  _et al._ (2009) A. H. Castro Neto, F. Guinea, N. M. R. Peres, K. S. Novoselov, and A. K. Geim, Rev. Mod. Phys. 81, 109 (2009).
  * Ribeiro  _et al._ (2009) R. M. Ribeiro, V. M. Pereira, N. M. R. Peres, P. R. Briddon, and A. H. C. Neto, New Journal of Physics 11, 115002 (2009).
  * John and Merlin (2016) R. John and B. Merlin, Crystal Structure Theory and Applications 5, 43 (2016).
  * Peng  _et al._ (2013) Q. Peng, X. Wen, and S. De, Rsc Advances 3, 13772 (2013).
  * Qin  _et al._ (2014) R. Qin, W. Zhu, Y. Zhang, and X. Deng, Nanoscale research letters 9, 1 (2014).
  * Liu  _et al._ (2014a) H. Liu, A. T. Neal, Z. Zhu, Z. Luo, X. Xu, D. Tománek, and P. D. Ye, ACS nano 8, 4033 (2014a).
  * Wang  _et al._ (2015b) L. Wang, A. Kutana, X. Zou, and B. I. Yakobson, Nanoscale 7, 9746 (2015b).
  * Wei and Peng (2014) Q. Wei and X. Peng, Applied Physics Letters 104, 251915 (2014).
  * Liu  _et al._ (2019) G. Liu, Z. Gao, and J. Zhou, Physica E: Low-dimensional Systems and Nanostructures 112, 59 (2019).
  * Li and Zhu (2015) X. Li and H. Zhu, Journal of Materiomics 1, 33 (2015).
  * Kang  _et al._ (2015) J. Kang, H. Sahin, and F. M. Peeters, Phys. Chem. Chem. Phys. 17, 27742 (2015).
  * Bertolazzi  _et al._ (2011) S. Bertolazzi, J. Brivio, and A. Kis, ACS Nano 5, 9703 (2011), pMID: 22087740.
  * Peng and De (2013) Q. Peng and S. De, Phys. Chem. Chem. Phys. 15, 19427 (2013).
  * Lu  _et al._ (2014) X. Lu, M. I. B. Utama, J. Lin, X. Gong, J. Zhang, Y. Zhao, S. T. Pantelides, J. Wang, Z. Dong, Z. Liu, W. Zhou, and Q. Xiong, Nano Letters 14, 2419 (2014).
  * Yoo  _et al._ (2018) Y. Yoo, J.-H. Yang, and J.-H. Lee, Current Applied Physics 18, 799 (2018).
  * Wang  _et al._ (2019) X. Wang, Y. Hong, M. Wang, G. Xin, Y. Yue, and J. Zhang, Physical Chemistry Chemical Physics 21, 9159 (2019).
  * Yang  _et al._ (2017) Y. Yang, X. Li, M. Wen, E. Hacopian, W. Chen, Y. Gong, J. Zhang, B. Li, W. Zhou, P. M. Ajayan, _et al._ , Advanced Materials 29, 1604201 (2017).
  * Park  _et al._ (2017) J. Park, M. S. Kim, E. Cha, J. Kim, and W. Choi, Scientific reports 7, 1 (2017).
  * Liu  _et al._ (2014b) K. Liu, Q. Yan, M. Chen, W. Fan, Y. Sun, J. Suh, D. Fu, S. Lee, J. Zhou, S. Tongay, J. Ji, J. B. Neaton, and J. Wu, Nano Letters 14, 5097 (2014b).
  * Deng  _et al._ (2018a) S. Deng, L. Li, and M. Li, Physica E: Low-dimensional Systems and Nanostructures 101, 44 (2018a).
  * Chen  _et al._ (2018) J.-W. Chen, S.-T. Lo, S.-C. Ho, S.-S. Wong, X.-Q. Zhang, Y.-D. Liu, Y.-Y. Chiou, Y.-X. Chen, J.-C. Yang, Y.-C. Chen, _et al._ , Nature communications 9, 1 (2018).
  * Zeng  _et al._ (2015) F. Zeng, W.-B. Zhang, and B.-Y. Tang, Chinese Physics B 24, 097103 (2015).
  * Ding  _et al._ (2019) W. Ding, D. Han, J. Zhang, and X. Wang, Materials Research Express 6, 085071 (2019).
  * Kliche (1985) G. Kliche, Journal of Solid State Chemistry 56, 26 (1985).
  * Du  _et al._ (2018) J. Du, P. Song, L. Fang, T. Wang, Z. Wei, J. Li, and C. Xia, Applied Surface Science 435, 476 (2018).
  * Deng  _et al._ (2018b) S. Deng, L. Li, and Y. Zhang, ACS Applied Nano Materials 1, 1932 (2018b).
  * Yang  _et al._ (2014) S. Yang, S. Tongay, Y. Li, Q. Yue, J.-B. Xia, S.-S. Li, J. Li, and S.-H. Wei, Nanoscale 6, 7226 (2014).
  * Wang  _et al._ (2017) H. Wang, E. Liu, Y. Wang, B. Wan, C.-H. Ho, F. Miao, and X. G. Wan, Phys. Rev. B 96, 165418 (2017).