The Computational Complexity of Factored Graphs

We consider a highly natural class of factored problems where the instances are graphs, and the operations are well-studied graph products and unions. Our factored graphs consist of arbitrary combinations of graphs under the following (binary) operations. Unless otherwise stated, all graphs are directed and $(a,b)$ denotes an edge from $a$ to $b$.

1. 1.

   Cartesian Product. Given $A,B$, the Cartesian product $A\mathrm{\square }B$ has vertices $(a,b)$ for $a\in A,b\in B$ and there is an edge from $(a,b)$ to $(c,d)$ if either 1) $a=c$ and $(b,d)\in E(B)$, or 2) $(a,c)\in E(A)$ and $b=d$.

2. 2.

   Tensor Product. Given $A,B$, the tensor product $A\times B$ has vertices $(a,b)$ for $a\in A,b\in B$ and there is an edge from $(a,b)$ to $(c,d)$ if $(a,c)\in E(A)$ and $(b,d)\in E(B)$.

3. 3.

   Union. Given $A,B$, the union $A\cup B$ has vertices $x\in V(A)\cup V(B)$ and there is an edge from $x$ to $y$ if $(x,y)\in E(A)\cup E(B)$.

A factored graph $G$ can be defined by an ordered tree $T(G)$, where internal nodes are labelled by one of the above three operations $\mathrm{\square },\times ,\cup$ and leaves are labelled with (possibly identical) input graphs. Since each operation is associative, we in fact allow the internal nodes to have arbitrary degree.²²2We require each internal node to have degree greater than 1, as otherwise the operation is the identity. We say that a factored graph $G=f(G_1,\mathrm{\dots },G_k)$ is of complexity $(n,k)$ if the tree has $k$ leaves and each input graph has at most $n$ vertices. Here, we stress that the we parameterize by the number of leaves in $T(G)$, regardless of the fan-in of specific internal nodes or if a certain input graph appears in multiple leaf nodes. As an example, both $(A\times B)\times A$ and $A\times B\times A$ are factored graphs of complexity $(n,3)$, where $n=\max (|V(A)|,|V(B)|)$. We illustrate their tree structures in Figure 1.

As another example, any graph $G$ can be represented by a factored graph of complexity $(2,|E(G)|)$ by taking a union over all edges of the graph.

We define a factored component of $G$, denoted $G_F$, as follows. $G_F$ is defined by an ordered tree $T(G_F)$, which is obtained from $T(G)$ by deleting every internal node $v$ labeled by $\cup$ and attaching exactly one child of $v$ to its parent. Another way to understand this is that, since the union and product operations obey the distributive law, we can recursively apply this law to convert a factored graph formula into a union of products. Then, each of these product terms is a factored component. The vertices of $G_F$ are $k_F$-tuples (note $k_F\le k$, where $k_F$ is the number of leaves of $T(G_F)$ and $k$ is the number of leaves of $T(G)$). We emphasize that the vertices are flattened tuples and do not preserve the topology of $T(G_F)$ beyond the order of the leaves. We call $k_F$ the dimension of the factored component $G_F$. The edges of $G_F$ are determined by $T(G_F)$ according to the definition of the graph operations $\mathrm{\square }$ and $\times$.

The vertex and edge sets of $G$ are then given by the union of the vertex and edge sets of the factored components. While a vertex may belong to multiple factored components, they must all have the same dimension, allowing us to define the dimension of a vertex (Definition 14). We also observe that $G$ has at most $2^k$ factored components. We give a more formal definition of factored graphs as well as simple examples in Section 2.

Our first result provides an unconditional hardness for a natural parameterized version of the well-studied Lexicographically First Maximal Independent Set (LFMIS) problem. The standard decision version of the LFMIS problem takes as input a graph $G=(V(G),E(G))$, where the vertices are indexed as $V(G)=\{0,1,\mathrm{\dots },|V(G)|-1\}$, and a special vertex $s\in V(G)$. The problem asks whether $s$ belongs to the LFMIS of $G$. In the parameterized version, the input is given as a factored graph $G=f(G_1,\mathrm{\dots },G_k)$ and the vertex indices are provided only for each graph factor $V(G_i)=\{0,1,\mathrm{\dots },|V(G_i)|-1\}$. To recover the indices for $V(G)$, recall that each vertex in the factored graph $G$ is a flattened tuple of numbers $(v_1,\mathrm{\dots },v_{k^{\prime }})$ for some $k^{\prime }\le k$, and therefore, we define the vertex indices to be given according to the standard lexicographic order of these tuples, with the index 0 given to the vertex with the lowest lexicographic order. In this work, we show that the LFMIS problem on factored graphs is $\mathrm{𝐗𝐏}$-complete under $\mathrm{𝐅𝐏𝐓}$-reductions³³3See Definition 9.3 [27]. Also formally stated in Definition 20 in the context of factored graph problems. and therefore unconditionally not in $\mathrm{𝐅𝐏𝐓}$, providing a lower bound on the best possible exponent as a function of $k$. LFMIS is a natural $𝐏$-complete problem [18], studied by [58, 59, 60] including in the parallel setting [20, 50, 12, 8]. We use the $𝐏$-completeness of this problem as an intuition for why the factored version might be difficult ($\mathrm{𝐗𝐏}$-complete), but we know of no direct connection between $𝐏$-completeness and hardness of the factored version.

While many works in parameterized complexity gave conditional lower bounds against problems in $\mathrm{𝐅𝐏𝐓}$ [25], for example completeness for the W-hierarchy [25, 26, 28] or the A-hierarchy [32], unconditional lower bounds against natural problems in $\mathrm{𝐅𝐏𝐓}$ are relatively rare [27]. Moreover, although it is known that $\mathrm{𝐅𝐏𝐓}⊊\mathrm{𝐗𝐏}$ via a diagonalization argument, the literature on $\mathrm{𝐗𝐏}$-complete problems remains sparse. The “pebble game” problem was first introduced by Kasai, Adachi, and Iwata [45]. Its parameterized version, the “$k$-pebble game”, was one of the earliest natural combinatorial problems shown to require $\mathrm{\Omega }(n^k)$ time and be $\mathrm{𝐗𝐏}$-complete [1]. As an application of the $k$-pebble game, some other game problems, such as the “cat and mouse game” [13] and the “$k$-peg game”, have also been proven to be $\mathrm{𝐗𝐏}$-complete via reductions from the $k$-pebble game problem [1]. More recently, Berkholz established an unconditional lower bound of $O(n^{(k-3)/12})$-time for the existential $k$-pebble game [6]. Our result provides yet another natural example of an $\mathrm{𝐗𝐏}$-complete problem with an explicit lower bound of $n^{\mathrm{\Omega }(\sqrt{k})}$.

In contrast to the LFMIS problem on factored graphs, we show that the well-studied problem of clique counting [51] is in $\mathrm{𝐅𝐏𝐓}$, solvable in a fixed polynomial of the input graph sizes (where the exponent possibly depends on the size of the clique of interest) times some function on the number of input graphs. Subgraph counting (in particular clique counting) has been studied by a long line of works [51, 16, 11, 42] in a variety of computational models [21, 24, 2, 56, 39]. On graphs with $n$ vertices, $s$-cliques can be counted in $O(n^s)$ time (and $n^{\mathrm{\Omega }(s)}$ time is necessary under standard hardness assumptions). We show that counting $s$-cliques on factored graphs of complexity $(n,k)$ is in $O(g(s,k)n^s)$ time for some fixed (large) function $g$. Note that we do not show clique counting is in $\mathrm{𝐅𝐏𝐓}$ with respect to the clique size parameter $s$, but only with respect to the complexity of the factored graph $k$.

Finally, we turn to the problem of reachability, one of the most fundamental computational problems on graphs. On an explicit graph, algorithms such as depth-first search (DFS) and breadth-first search (BFS) compute reachability in linear time. This raises the question: can reachability on factored graphs be computed efficiently? Moreover, reachability is closely related to classic space complexity classes. The general reachability problem is an important $\mathrm{𝐍𝐋}$-complete problem [57, 43]; meanwhile, Cook and Mckenzie showed that reachability on a directed acyclic graph of outdegree at most one is $𝐋$-complete [19]. This naturally gives rise to another question: does the completeness of reachability for a classic complexity class extend to its parameterized counterpart when the inputs are given as factored graphs, similar to what we have seen in the case of LFMIS in Theorem 1?

Indeed, we show that the parameterized version of reachability on factored graphs is $\mathrm{𝐗𝐍𝐋}$-complete under $\mathrm{𝐅𝐏𝐓}$-reductions, where $\mathrm{𝐗𝐍𝐋}$ is the class of parameterized problems solvable in nondeterministic logarithmic space for any fixed parameter $k$. On the other hand, while we cannot provide a definitive answer to whether reachability on factored graphs is in $\mathrm{𝐅𝐏𝐓}$, we show that answering this question would exactly resolve a major open problem in classical complexity theory. Specifically, we establish a parameterized analog of the well-known open problem that asks whether $\mathrm{𝐍𝐋}\subseteq \mathrm{𝐃𝐓𝐈𝐌𝐄}(n^C)$ for some fixed constant $C$.

This result also has several further implications. First, we observe that if reachability is not in $\mathrm{𝐅𝐏𝐓}$, $\mathrm{𝐍𝐒𝐏𝐀𝐂𝐄}(h(n))⊈𝐏$ for any space-constructible $h(n)=\omega (\log n)$. On the other hand, if reachability is in $\mathrm{𝐅𝐏𝐓}$ then the Exponential Time Hypothesis (ETH) is false. In particular, we claim that since $k$-SUM (determining if in a set of $n$ numbers of $O(k\log n)$ bits there is a subset of $k$ numbers summing to zero) is in $\mathrm{𝐍𝐋}$, then $k$-SUM can be solved in $O\left(n^C\right)=n^{o(k)}$ time, and therefore ETH is false [55].⁴⁴4We need $O(k^2\log n)$ bits to verify that $k$ numbers of $O(k\log n)$ bits sum to zero. Finally, by combining the above implications, one can also conclude that if ETH is true, then $\mathrm{𝐍𝐒𝐏𝐀𝐂𝐄}(\omega (\log n))⊊𝐏$, a result that, to the best of our knowledge, has not been previously established.

Parameterized space complexity classes, including XL and XNL, have also been studied extensively in the literature [10, 17, 33, 29]. Chen, Flum, and Grohe introduced the first complete problems for XL and XNL under parameterized-logspace-reductions⁵⁵5Also known as PL-reductions, a more restrictive notion compared to $\mathrm{𝐅𝐏𝐓}$-reductions [17]. In a related direction, [9] identified a wide variety of problems complete for the class XNLP, which is the class of parameterized problems solvable in nondeterministic logarithmic space and polynomial time for each parameter. Most relevant to our result, Elberfeld, Stockhusen, and Tantau also showed that a parameterized version of reachability with multi-colored edges is complete for the class parameterized-NL-cert under PL-reductions [29].

A long line of work, initiated by [25, 26, 28, 32], has studied the complexity of parameterized problems as a function of their input size and a parameter. Within parameterized complexity, a common theme is to study the complexity of problems given succinct representations of their input. For example, several previous works have investigated the complexity of computing Nash equilibrium of succinct games (represented implicitly) [31, 23, 22, 34, 53, 36]. As another example, [62] considers the complexity of combinatorial problems with succinct representation. Similarly, [52, 63, 40, 41, 49, 48, 14, 15] study the complexity of various computational problems on periodic structures, i.e., travel schedules on a periodic timetable.

Most relevant to this paper, several works have investigated computational problems on graphs with succinct representations such as small circuits [35], distributed graphs described by low complexity agents [4], and factored problems [21]. However, none of these works consider the complexity of factored graphs formed under graph products.

On the subject of succinct representations, researchers have also studied how to represent graphs as efficiently as possible [44, 38, 5, 30, 7, 47, 54].

We begin with the definitions of the relevant graph operations. Let $G$ and $H$ be two directed graphs.

As a simple example, note that the Cartesian product of two paths is a grid.

While there are many other graph products and operations to consider, such as the or product, or graph negation, we will primarily focus our study of factored graphs under the above three operations.

We note that the above three operations are associative, and observe that the products of higher arity are given as follows.

We now describe how the above operations construct factored graphs. Formally, we define a factored graph by describing how the above graph operations combine the input graphs into a single graph. This motivates the definition of a factored graph according to a tree which specifies the order of operations, or the tree structure of a factored graph.

To illustrate our definitions, we will use the following example of a factored graph $G=((A\times B)\cup C)\mathrm{\square }(D\times (E\cup F))$. Note that there is a natural correspondence between the tree structures of factored graphs and the formulas of the above form, by using parentheses to delineate subtrees of the tree structure. The tree structure of $G$ is given in Figure 2.

We now describe how the vertex and edge sets of a factored graph are obtained from its tree structure. First, we define factored components of factored graphs.

In our example, the factored components are $(A\times B)\mathrm{\square }(D\times E),(A\times B)\mathrm{\square }(D\times F),C\mathrm{\square }(D\times E)$, and $C\mathrm{\square }(D\times F)$, with dimensions $4,4,3,3$, respectively. Some example tree structures of factored components are given in Figure 3.

Here, we emphasize that the vertex sets of the factored components are flattened products of the vertex sets of the graphs labeling the leaves. For example, the vertex of the factored component $(A\times B)\mathrm{\square }(D\times E)$ has the form $(a,b,d,e)$ not $((a,b),(d,e))$. In particular, the vertex sets do not depend on the topology of the tree beyond the order of the leaves. Finally, the vertex and edge set of $G$ is simply the union of the factored components.

We note here that different factored graphs can have identical vertex and edge sets. For example, $G_1=(H_1\times H_2)\times H_3$ and $G_2=H_1\times (H_2\times H_3)$ both have vertex set ${\prod }_{i=1}^3{H}_i$ and edges from $(h_1,h_2,h_3)$ to $(h_1^{\prime },h_2^{\prime },h_3^{\prime })$ if and only if $(h_i,h_i^{\prime })\in E(H_i)$ for all $i$. This aligns with our expectation, as the tensor product is associative.

Note that a single vertex in $G$ can belong to multiple factored components. In our running example, if there is a vertex $x\in V(E)\cap V(F)$, then the vertex $(c,d,x)$ is in the factored components corresponding to $C\mathrm{\square }(D\times E)$ and $C\mathrm{\square }(D\times F)$. However, both factored components have dimension $3$. This is formalized in the following lemma, which follows directly from the construction of factored graphs.

This allows us to define the dimension of a vertex $dim(v)$ as the dimension of any factored component it belongs to.

By construction, the endpoints of any edge must belong to the same factored component.

As a corollary, we show that there are no edges between vertices of different dimensions, since vertices in the same factored component necessarily have the same dimension.

Finally, since every vertex has a unique dimension, it is clear that vertex dimension partitions the vertices of the factored graph. Thus, vertex dimension induces an equivalence relation on $V(G)$.

In this section, we review the parameterized complexity classes relevant to this paper with respect to problems on factored graphs. We begin with the definition of fixed-parameter tractability ($\mathrm{𝐅𝐏𝐓}$).

We also study the parameterized complexity classes $\mathrm{𝐗𝐏}$ and $\mathrm{𝐗𝐍𝐋}$, which correspond to the parameterized version of the classical complexity classes $𝐏$ and $\mathrm{𝐍𝐋}$, respectively. More generally, one can define the parameterized version $\mathrm{𝐗𝐂}$ for any classical complexity class $𝐂$ as follows [27]: a parameterized language $L\in \mathrm{𝐗𝐂}$ if and only if $L_k\in 𝐂$ for every parameter $k$. Here, $L_k$ is referred to as the $k$-th slice of $L$, which is the subset of $L$ consisting of all instances with parameter $k$. We now give the definitions of $\mathrm{𝐗𝐏}$ and $\mathrm{𝐗𝐍𝐋}$ in the context of factored graph problems.

Finally, for $\mathrm{𝐗𝐏}$- and $\mathrm{𝐗𝐍𝐋}$-completeness, we follow the usual definition that a problem is considered to be complete for a complexity class C if it belongs to C and is hard for C under some suitable notion of reductions. Here, we use the standard notion of parameterized mapping reduction (see Definition 9.3 in [27]), also known as the $\mathrm{𝐅𝐏𝐓}$-reduction [17], under which the class $\mathrm{𝐅𝐏𝐓}$ is closed. We now give a definition for $\mathrm{𝐗𝐏}$- and $\mathrm{𝐗𝐍𝐋}$-hardness under this reduction in the context of factored graph problems.

Recall that our first main result is the $\mathrm{𝐗𝐏}$-completeness of the LFMIS problem on factored graphs.

See 1

Theorem 1 is a consequence of a generic reduction from an arbitrary language $L\in \mathrm{𝐃𝐓𝐈𝐌𝐄}(n^{\mathrm{\ell }})$ to the LFMIS problem on factored graphs. Specifically, given a language $L\in \mathrm{𝐃𝐓𝐈𝐌𝐄}(n^{\mathrm{\ell }})$ and the corresponding Turing machine that decides $L$ in $O(n^{\mathrm{\ell }})$ time, we construct a factored graph $G$ of complexity $(O(n),O({\mathrm{\ell }}^2))$ using $O({\mathrm{\ell }}^2{n}^2)$ time, such that solving the LFMIS on $G$ simulates the Turing machine $M$. Then, it is fairly straightforward from this reduction that the problem is $\mathrm{𝐗𝐏}$-complete. Moreover, we also obtain the explicit lower bound of $n^{\mathrm{\Omega }(\sqrt{k})}$ by an application of the Time Hierarchy Theorem to the reduction.

Before proceeding to the detailed explanation, we first provide a high level intuition of this construction. Given a Turing machine, we can encapsulate its computation history in a matrix, where each row represents a configuration of the Turing machine at a specific time. The key idea of the reduction is to construct a graph in such a way that selecting vertices for the LFMIS corresponds to recovering the matrix entries, and thereby simulating the machine. To achieve this, we construct a graph with a grid structure mirroring the matrix. At each grid point, we place a collection of vertices representing all the possible choices for the corresponding matrix entry. The edges are defined according to the machine’s transition function to ensure that the LFMIS chooses the single correct vertex from each grid point that agrees with the computation history of the Turing Machine, effectively allowing us to simulate the Turing machine by solving the LFMIS on the graph. It turns out that this graph has a highly regular structure and therefore can be factorized into a more succinct representation. In the remainder of this (sub)section, we explain this reduction in further detail.

Let $L$ be a language in $\mathrm{𝐃𝐓𝐈𝐌𝐄}(n^{\mathrm{\ell }})$ and let $M$ be the corresponding Turing machine that decides $L$ in time $O(n^{\mathrm{\ell }}).$ Given an input $x$ to $M$, if $M$ halts within time $T$, then the entire computation history of $M$ on $x$ can be represented by a $T\times T$ matrix $W$, where the $i$-th row of $W$ represents the configuration of $M$ at time $i$. To achieve this, each entry $W_{i,j}$ contains the following information about the $j$-th tape cell at time $i$: 1) the symbol occupying the cell, 2) whether the tape head is over the cell, and 3) the machine’s current state if the tape head is over the cell. The goal now is to define a graph $G$ such that the LFMIS of $G$ recovers the computation history $W$, thereby simulating the machine $M$. We modify the Turing machine so that it suffices to query a single vertex in the graph for the halting state of $M$.

In contrast to the first result, our second main result states that counting cliques on factored graphs is in $\mathrm{𝐅𝐏𝐓}$. For this result, we assume that all graphs are undirected.

See 2

In the technical overview, we use edge counting ($s=2$) as an illustrative example. Note that if $(u,v)$ is an edge, $u,v$ must have the same dimension (Corollary 16), so we may count the edges in each dimension separately. Thus, fix a dimension $d\le k$.

There are at most $2^k$ factored components of dimension $d$. While some edges may belong to multiple factored components, we can use the inclusion-exclusion principle to avoid double-counting such edges. In particular, it suffices to consider counting the number of edges in an arbitrary intersection of factored components $G_{F_1}\cap \mathrm{\dots }\cap G_{F_m}$. Note that the number of such intersections, while being a large function of $k$, is crucially independent of $n$.

Fix such an intersection and consider a pair of vertices $u,v$ with $u=(u_1,\mathrm{\dots },u_d)$ and $v=(v_1,\mathrm{\dots },v_d)$. Note that by determining whether $u_i,v_i$ are equal or adjacent for all $i\in [k]$, we can infer from the factored graph tree structure whether $(u,v)\in E(G)$. Thus, we can categorize all pairs of vertices into $2^{2k}$ groups based on the relations $u_i=v_i$ and $(u_i,v_i)\in E(G_i)$. Note also that these groups are disjoint. Next, we collect the subset of groups that form edges in the current intersection $G_{F_1}\cap \mathrm{\dots }\cap G_{F_m}$. To count the number of edges, it then suffices to sum up the sizes of each group in this collection. For a given group, we can determine its size in $O(k{n}^2)$ time since the relations on each coordinate are independent. In particular, we can count the number of pairs of vertices in each input graph satisfying the relevant constraints and take the product over all input graphs.

Finally, we study the reachability problem on factored graphs.

See 3

We begin with an overview of the proof for the $\mathrm{𝐗𝐍𝐋}$-completeness result, followed by that for the equivalence result. In fact, we will see that both proofs rely on the same major building blocks in slightly different ways.