<p>It is NP-complete to determine whether a tree can be embedded into the two-dimensional integer grid, with the tree vertices placed on distinct grid points and the tree edges placed on grid edges.</p>

<p>See e.g. Gregori, <a href="http://dx.doi.org/10.1016/0020-0190%2889%2990118-X">IPL 1989</a>.</p>

CC BY-SA 4.0
2018-08-12T10:05:03.817Z
Oh, the input tree is also a binary tree. That's great!
Cyriac Antony
CC BY-SA 2.5
2010-09-13T01:55:48.283Z
So, this implies the hardness of rectilinear drawing of trees? Is there a degree bound that preserves hardness?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-13T02:14:05.530Z
Re the degree bound: if there exists a vertex of degree greater than four, then no grid embedding is possible.
David Eppstein
CC BY-SA 2.5
2010-09-13T03:23:32.070Z
Thanks David, simple to state yet an interesting problem.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-13T00:32:09.133Z
2010-09-13T00:32:09.133Z
David Eppstein
<p>One of the hardest problems on trees is minimum bandwidth problem. It is $NP$-hard on trees of maximum degree 3. Also it is NP-hard on circular caterpillar of hair length 1.</p>

<p>References:</p>

<p>Michael R. Garey, Ronald L. Graham, David S.Johnson, and Donald E. Knuth. Complexity results
for bandwidth minimization. SIAM J. Appl. Math., 34(3):477-495, 1978.</p>

<p>Burkhard Monien. The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods, 7(4):505-512, 1986.</p>

<p>W. Unger. The complexity of the approximation of the bandwidth problem. In FOCS, pages
82–91, 1998</p>

CC BY-SA 3.0
2014-02-15T14:53:49.840Z
The corrected version of Unger's paper is *Hardness results for approximating the bandwidth*, Chandan Dubey, Uriel Feige, and Walter Unger.
Yuval Filmus
CC BY-SA 2.5
2010-09-12T23:07:57.890Z
2010-09-12T23:22:29.277Z
2010-09-12T23:22:29.277Z
Mohammad Al-Turkistany
<p>Group Steiner problem is a nice example. The input to this problem is an undirected edge-weighted graph $G=(V,E)$ and k groups of vertices $S_1, S_2, \ldots, S_k$. The goal is to find a minimum weight tree that contains at least one vertex from each group. It is easy to see that the Set Cover problem is a special case even when G is a star. Thus the problem is hard to approximate to within a $O(\log n)$ factor unless P=NP. Moreover, it was shown by Halperin and Krauthgamer that the problem is hard to approximate to within an $O(\log^{2-\epsilon} n)$ factor for any fixed $\epsilon > 0$ unless NP has randomized quasi-polynomial time algorithms (see the paper for a precise statement). There is an $O(\log^2 n)$ approximation on trees by Garg, Konjevod and Ravi.</p>

CC BY-SA 2.5
2010-09-13T03:04:27.063Z
Aaah: the unformatted latex !! it hurts the eyes :)
Suresh Venkat
CC BY-SA 2.5
2010-09-13T12:33:58.723Z
Well, I don't know how to do latex formatting here :). Pointers??
Chandra Chekuri
CC BY-SA 2.5
2010-09-18T06:11:11.900Z
just use \$..\$ as usual.
Suresh Venkat
CC BY-SA 2.5
2010-09-18T06:12:49.830Z
ok all fixed now.
Suresh Venkat
CC BY-SA 2.5
2010-09-13T02:56:05.927Z
2010-09-18T06:12:35.260Z
2010-09-18T06:12:35.260Z
Chandra Chekuri
<p>The firefighter problem has received a fair amount of attention recently, and is (somewhat surprisingly) <a href="http://www.sciencedirect.com/science/article/pii/S0012365X0600776X">NP-hard on trees of maximum degree 3</a>.  It is actually a fairly natural question, described as follows:</p>

<p>A fire breaks out at the root of the tree (or more generally, a specified vertex in a graph).  At every step, the firefighter protects one non-burning vertex, after which time the fire spreads to every unprotected neighbour.  The process ends when there is no unprotected vertex next to the fire.  Is there a strategy for the firefighter in which at most $k$ vertices burn?</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/S0012365X09002672">Or a variant, also NP-hard</a>: Is there a strategy for the firefighter in which no leaf burns?</p>

CC BY-SA 3.0
2012-11-09T19:14:00.577Z
2012-11-09T19:14:00.577Z
Andrew D. King
<p>The unweighted edge multicut problem is the following: Given an undirected graph <span class="math-container">$G$</span>, a collection of pairs of vertices of <span class="math-container">$G$</span>, and a positive integer <span class="math-container">$k$</span>, find if there is a subset <span class="math-container">$S$</span> of at most <span class="math-container">$k$</span> edges in <span class="math-container">$G$</span> whose removal disconnects every pair of vertices in the collection.</p>
<p>This problem is NP-hard (and MAX SNP-hard) on <em>stars</em> [<a href="https://doi.org/10.1007/BF02523685" rel="nofollow noreferrer">1</a>].</p>
<p>[<a href="https://doi.org/10.1007/BF02523685" rel="nofollow noreferrer">1</a>] Garg, Vazirani, and Yannakakis, <a href="https://doi.org/10.1007/BF02523685" rel="nofollow noreferrer">Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees</a>, Algorithmica, 18(1), pp 3-20, 1997.</p>

CC BY-SA 4.0
2010-09-13T00:20:19.020Z
2022-10-27T13:33:06.647Z
2022-10-27T13:33:06.647Z
gphilip
<p>A harmonious coloring of a simple graph is a proper vertex coloring such that each pair of colors appears together on at most one edge. The Harmonious Chromatic Number of a graph is least number of colors in a harmonious coloring of the graph. This problem of finding Harmonious Chromatic Number was shown to be NP-complete on trees by <a href="http://www.sciencedirect.com/science/article/pii/0166218X9400100R">Edwards and McDiarmid</a>. In fact, they also show that the problem remains NP-complete for trees of radius 3. </p>

CC BY-SA 3.0
2014-02-15T09:28:44.360Z
2014-02-15T09:28:44.360Z
Ashutosh Rai
<p>Given a tree $T$, a partition of $V(T)$ in $k$ levels $\phi: V(T)\to \{1,\ldots, k\}$
(i.e., edges of $T$ connect vertices of neighbouring levels $i$ and $i+1$), and an
integer $K$. Can you permute the vertices inside the levels such that the crossing number
is at most $K$?</p>

<p>This problem is NP-complete, proved by Martin Harrigan and Patrick Healy,
<a href="http://link.springer.com/chapter/10.1007/978-3-642-19094-0_9">$k$-Level Crossing Minimization Is NP-Hard for Trees</a>,
WALCOM 2011, LNCS 6552, pp. 70–76.</p>

CC BY-SA 3.0
2013-07-07T14:55:19.180Z
2013-07-07T14:55:19.180Z
user13136
<p>A problem that one might think would NOT be hard on trees, but is, is the <a href="http://maven.smith.edu/~orourke/TOPP/P35.html">freeze-tag problem in computational geometry</a>: briefly, the problem of scheduling wakeups for robots starting with a single awake 'bot, where makespan is the cost measure. </p>

<p>It's known to be NP-hard on weighted star graphs. However, it's open whether the problem is NP-hard in the plane. One might argue that the NP-hardness comes not from 'tree-ness', but from 'arbitrary metric'-ness, but star graphs only give you a limited space of metrics..</p>

CC BY-SA 2.5
2010-09-12T23:31:25.700Z
2010-09-12T23:31:25.700Z
Suresh Venkat
<p>Empire colouring is NP-hard for trees.</p>

<p>Let $r$ and $s$ be fixed positive integers, and let $G$ be a graph whose vertex set is 
partitioned into blocks (or empires) each containing exactly $r$ vertices. The $(s, r)$-colouring
problem $s$-$\text{COL}_r$ asks for a colouring of the vertices of the graph $G$ that 
uses at most $s$ colours, never assigns the same colour to adjacent vertices in different 
empires and, conversely, assigns the same colour to all vertices in the same empire, 
disregarding adjacencies.</p>

<p>McGrae and Zito, Empires make cartography hard: The complexity of the empire colouring problem, 
<a href="http://link.springer.com/chapter/10.1007/978-3-642-25870-1_17">LNCS 6986</a> (2011) 179–190, 
show that, for trees, $s$-$\text{COL}_r$ is NP-hard for $s \in \{3,\ldots, 2r − 1\}$ 
(and solvable in polynomial time for other positive values of $s$.)</p>

CC BY-SA 3.0
2013-12-20T17:15:53.077Z
2013-12-20T17:15:53.077Z
Jens G.
<p>A flow in a network is confluent if it uses at most one outgoing arc at each node. 
NP-hardness of determining a maximum confluent flow in a tree (of diameter 4, 
with multiple sinks allowed) is proved in: 
<a href="http://link.springer.com/book/10.1007/978-3-642-13073-1/page/2">D. Dressler and M. Strehler, Capacitated Confluent Flows: Complexity and Algorithms, LNCS 6078 (2010) 347-358</a>.</p>

CC BY-SA 3.0
2013-06-12T16:47:09.827Z
2013-06-12T16:47:09.827Z
Tobias Müller
<p><a href="http://dx.doi.org/10.1137/S0097539794269461">Maximum leaf-labeled isomorphic subtree</a>.
The input is a set $TS$ of leaf-labeled tree (internal nodes are not labeled).
A solution is any tree $T$ such that for each tree $T_1\in TS$ then $T$ is isomorphic to a subtree of $T_1$.
The optimal solution is the one that maximizes the number of leaves of $T$.</p>

<p>The problem is NP-hard (actually, it is hard to approximate) only when all input trees have unbounded degree.</p>

CC BY-SA 2.5
2010-09-13T08:04:11.470Z
2010-09-13T08:04:11.470Z
Gianluca Della Vedova
<p>The Travelling Repairman Problem (TRP) is known to be NP-hard on weighted trees. In this problem, which is also sometimes called the Minimum Latency Problem, the goal is to find a tour that visits all the vertices of a graph while minimizing the average latency. The latency of a vertex $u$ is the cost of the tour from the origin until the tour visits $u$.</p>

<p>Note that in the related (and more famous) TSP problem, the goal is to minimize the maximum, rather than the average latency. I think the TRP is generally considered a more complicated problem (in fact TSP is in P for tree metrics).</p>

<p>NP-hardness on trees was shown in R.A. Sitters "The Minimum Latency Problem Is NP-Hard for Weighted Trees", ISCO 2002.</p>

CC BY-SA 3.0
2014-01-04T16:31:01.537Z
That is a nice Problem!
Tayfun Pay
CC BY-SA 3.0
2014-01-04T15:01:16.330Z
2014-01-04T15:01:16.330Z
Michael Lampis
<p>Graph Motif is NP-Complete problem on trees of maximum degree three:</p>
<p>Fellows, Fertin, Hermelin and Vialette, <a href="https://doi.org/10.1007/978-3-540-73420-8_31" rel="nofollow noreferrer">Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs</a>
<a href="https://doi.org/10.1007/978-3-540-73420-8_31" rel="nofollow noreferrer"></a>Lecture Notes in Computer Science, 2007, Volume 4596/2007, 340-351</p>

CC BY-SA 4.0
2010-09-18T06:10:06.277Z
2022-11-08T08:10:23.613Z
2022-11-08T08:10:23.613Z
Mohammad Al-Turkistany
<p>A graph $G(V, E)$ is 2-splittable if it is possible to partition its edge set into two subsets such that the induced subgraphs are isomorphic. Deciding whether a given graph is 2-splittable is $NP$-complete even if input is restricted to trees.</p>

<p>Formally, the problem is:</p>

<p><strong>PARTITIONED GRAPH ISOMORPHISM</strong></p>

<p>INSTANCE: A tree $T = (V,E)$</p>

<p>QUESTION: Is there a partition $\{E1,E2 \}$ of $E$ such that the two forests $T1 = (V,E1)$ and $T2 = (V,E2)$ are isomorphic?</p>

<p>The NP-completeness column cites the unpublished manuscript of Graham and Robinson, "Isomorphic factorization IX: even trees".</p>

<p>D.S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms 3
(1982), 288–300</p>

CC BY-SA 3.0
2014-01-03T23:26:49.580Z
2015-08-13T03:17:34.193Z
2015-08-13T03:17:34.193Z
Mohammad Al-Turkistany
<p>There's a (very general) problem I had a look at as part of a project: a variant of this problem remains NP-hard even on graphs with two vertices and a single edge, and a different variant is NP-hard on trees. Since the NP-hardness of the first variant obviously doesn't stem from the shape of the graph, the second is probably more interesting.</p>

<p>The problem is the distribution of files on and the routing of downloads in a network (for instance, the intranet of a company). Let $S$ be a set of servers and $C$ be a set of clients. Let $G=(V,E)$ be a graph such that $S \subset V$, $C \subset V$ and $S \cap C = \emptyset$ (so servers and clients are vertices, but there can be vertices that are not servers or clients, think of them as routers). Every $s \in S$ has a capacity (think the size of the harddrives), denoted as $|s|$. Let $F$ be a set of files, where every $f \in F$ has a filesize, denoted as $|f|$. Every $e \in E$ has a throughput, denoted as $t_e$. We also have a set of requests $R \subseteq C \times F$, where each $(c,f) \in R$ means that client $c$ wants to download file $f$.</p>

<p>The problem is to find for each server $s \in S$ a set of files $A_s$ such that $\sum_{f \in A_s} |f| \leq |s|$ (so to add files to servers without the total filesize exceeding the capacity of the server), and to find a path $P_r$ in $G$ for every request $r = (c,f) \in R$ such that the path starts at $c$ and ends at a server $s$ with $f \in A_s$, such that if for some edge $e$, $D_e$ denotes the set of requests such that for all $r = (c,f) \in D_e$, $P_r$ contains $e$, then $\sum_{(c,f) \in D_e}|f| \leq t_e$ (so to route all requests on the graph such that no edge capacity is exceeded).</p>

<p>If you don't require all downloads to be routed but instead try to maximize the sum of the filesizes of the downloads that <em>are</em> routed you can easily reduce subset-sum to this problem: you have a single server with vast amounts of space, a single client connected to the server with an edge with a capacity equal to the target value of the subset-sum instance and for every integer in the subset-sum instance you create a file with equal size; the client then wishes to download all these files.</p>

<p>A (much?) more interesting variant for this question is the case that you try to minimize the number of edges whose capacity is exceeded - perhaps the network we are working on models the transatlantic internet cables and replacing a cable is so costly that the difference in cost of upgrade to a factor two faster and an upgrade to a factor three faster is negligible. We also say that the placements of files on the servers are already given and cannot be modified, so we look solely at the routing issues.</p>

<p>The set-cover problem can easily be reduced to this variant. We are given a set $U$ called the universe and several subsets $S \subseteq P(U)$ of this universe. We are asked to pick the smallest amount of subsets such that their union equals the universe. For every $u \in U$ we create a file of size 1. We have a single client that wants to download all these files.</p>

<p>For every subset $s \in S$, we create a 'cluster' of servers: a cluster consists of a single vertex (a router) connected to a number of servers such that the servers are only connected to the router. For every $u \in s$ we add a single server to the cluster with the file on it corresponding to $u$. These clusters are then connected to the client with an edge of capacity 1 (so each edge connects the client with the router for the cluster). Furthermore, for every server cluster we add one more server to that cluster hosting a single new file (unique to that cluster) of size 1. All these files (so, in addition to the files corresponding to elements of the universe) are requested by the client.</p>

<p>The idea is that the client needs the files that are unique for all the server clusters, so the edges connecting the client to the server clusters are already at the limit of their capacities (their capacities are 1, the files have size 1). If the client downloads any elements of the universe from any cluster, the edge connecting to that cluster becomes overloaded. Since we only require to minimize the <em>number</em> of overloads (and not by how much we exceed the capacities), the client can download the rest of the elements of the universe hosted at that server cluster (so the rest of the elements of the corresponding subset) without penalty. This therefore corresponds to the subset being chosen. The client wants to download all the files in the universe once, so the universe will indeed be covered, and to minimize the number of edges that are overloaded we need to minimize the number of subsets chosen.</p>

<p>Note that the above construction yields a tree graph, so it's an example of an NP-hard problem on trees.</p>

CC BY-SA 2.5
2010-09-13T01:14:54.177Z
2010-09-13T01:14:54.177Z
Alex ten Brink
<p>The Unsplittable Flow Problem. In fact UFP is hard even on a single edge (Knapsack).</p>

CC BY-SA 3.0
2012-11-09T17:31:18.623Z
2012-11-09T17:31:18.623Z
Arindam Pal
<p>Somehow i missed the Achromatic Number problem in the last answer, but this is one of the most natural problems i know of, which are NP-complete on trees.</p>

<p>A complete coloring of a graph is a proper coloring such that there is an edge between every pair of color classes. The coloring can be stated in contrast to Harmonious Coloring, as a proper coloring such that each pair of colors appears on <em>at least</em> one edge. Also, it can be stated as a complete (or full) homomorphism to a clique. The Achromatic Number problem is a <em>maximization</em> problem, where we look for largest number of color classes in a complete coloring of the graph.</p>

<p>Yannakakis and Gravil proved this problem to be <a href="http://epubs.siam.org/doi/abs/10.1137/0138030" rel="nofollow">NP-hard on complement of Bipartite Graphs</a>. Cairnie and Edwards extended that result and showed that the problem is <a href="http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291097-0118%28199711%2926:3%3C129%3a%3aAID-JGT3%3E3.0.CO;2-T/abstract" rel="nofollow">NP-complete on trees</a>. </p>

<p>A lot of work has been done on this problem in the field of Approximation Algorithms  [<a href="http://www.researchgate.net/publication/2942749_Approximation_Algorithms_for_the_Achromatic_Number" rel="nofollow">3</a>,<a href="http://www.researchgate.net/publication/2942749_Approximation_Algorithms_for_the_Achromatic_Number" rel="nofollow">4</a>,<a href="http://www.sciencedirect.com/science/article/pii/0012365X81901643" rel="nofollow">5</a>]. </p>

CC BY-SA 3.0
2014-02-20T09:50:50.497Z
2014-02-20T09:50:50.497Z
Ashutosh Rai
<p>k-Balanced Partition Problem on graphs, in which one has to partition the $n$ vertices into $k$ connected components of size at most $\lceil\frac{n}{k}\rceil$ each and at the same time minimize the total cost of edges connecting vertices in different sets, called the cut cost.
This problem is actually APX-hard even on unweighted trees of constant maximum degree[<a href="http://lucafoschini.com/papers/Balanced_Algorithmica.pdf" rel="nofollow">1</a>].</p>

CC BY-SA 3.0
2016-03-17T11:45:35.083Z
2016-03-17T11:45:35.083Z
user1105
<p><em>Packing coloring</em> in NP-complete for trees, as proved in Fiala and Golovach, Complexity of the packing coloring problem for trees (2010). This problem was introduced under the name broadcast coloring by Goddard et al. motivated by an application in broadcast networks.</p>
<p>Packing <span class="math-container">$k$</span>-coloring is a partitioning of the vertex set of a graph into <span class="math-container">$k$</span> disjoints sets with the property that vertices in the <span class="math-container">$i$</span>th set have pairwise distance greater than <span class="math-container">$i$</span>.</p>
<p><em>Packing Coloring</em><br />
Instance: A graph <span class="math-container">$G$</span> and a positive integer <span class="math-container">$k$</span>.<br />
Question: Does <span class="math-container">$G$</span> allow a packing <span class="math-container">$k$</span>-coloring?</p>
<p>The packing chromatic number of trees of maximum degree three is at most 7, while it is unbounded for trees of maximum degree four. It is unknown to me whether <em>Packing coloring</em> is NP-complete for trees of maximum degree four.</p>

CC BY-SA 4.0
2024-12-14T10:45:52.563Z
2024-12-14T17:35:28.023Z
2024-12-14T17:35:28.023Z
Cyriac Antony
<p>Is Circuit SAT on trees NPC?. Tree inner vertices are labeled as OR/AND gates. Leaves are inputs. Determine if there is a satisfying set of inputs for the circuit to evaluate to True.</p>

<p>At first glance it seems you can solve bottom up, but constraints get nasty as you move up the tree and OR gates suddenly need one of the other $2^k - 1$ assignments.</p>

CC BY-SA 3.0
2016-03-17T15:10:43.847Z
Umm, circuits that are trees have a name: formulas. Formula SAT is of course NP-complete, as 3-SAT or even full CNF-SAT are its special cases.
Emil Jeřábek
CC BY-SA 3.0
2016-03-17T15:20:27.023Z
Formulas without repeated variables.
Chad Brewbaker
CC BY-SA 3.0
2016-03-17T15:30:19.597Z
How so? *All* formulas are trees. If you want to restrict multiple occurrences of variables, that’s an additional constraint. (I also assume that when you write “inputs”, you really mean “literals”, as Circuit SAT with only AND, OR, and positive literals is trivially polynomial-time to begin with.)
Emil Jeřábek
CC BY-SA 3.0
2016-03-17T15:48:44.257Z
a+b+c+a   (Variable a is repeated twice, thus DAG not tree).
Chad Brewbaker
CC BY-SA 3.0
2016-03-17T15:59:28.707Z
Certainly not under the standard terminology. The formulas $((a+b)+c)+d$ and $((a+b)+c)+a$ have the same underlying tree, only with different labels at one of the nodes. A tree stays a tree no matter how are its leaves relabelled.
Emil Jeřábek
CC BY-SA 3.0
2016-03-17T17:33:59.197Z
Emil is right. A formula like $(p \land q) \lor p$ is a tree. Fan-out does not apply to input gates in circuits. With your definition that a variable cannot appear both positively and negatively therefore the formula is trivially satisfiable.
Kaveh
CC BY-SA 3.0
2016-03-17T19:40:34.433Z
Implicit DAG in your example. Either you make the $p$ value form a diamond where it is referenced from two gates, or you cheat and and have an implicit constraint in the formula that both $p$ leaves must be assigned the same value.  Allowing constraints that certain inputs must be equivalent seems to unnecessarily complicate a nice toy problem.
Chad Brewbaker
CC BY-SA 3.0
2016-03-17T21:35:15.147Z
It is not a toy problem. This is the standard terminology, when when we say a circuit is a tree it does not mean variables appear only once. In any case and independent of what we call it the problem you proposing is trivial as I wrote.
Kaveh
CC BY-SA 3.0
2016-03-17T15:07:39.477Z
2016-03-17T15:07:39.477Z
Chad Brewbaker
<p>You can find &quot;natural&quot; and &quot;well-known&quot; examples of graph problems that are hard even if restricted to trees from <a href="https://www.csc.kth.se/%7Eviggo//wwwcompendium/" rel="nofollow noreferrer">our standard reference</a>. Examples:</p>
<ul>
<li><a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node121.html" rel="nofollow noreferrer">Integral <em>k</em>-multicommodity flow</a>,</li>
<li><a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node60.html" rel="nofollow noreferrer">Common embedded subtree</a>,</li>
<li><a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node168.html" rel="nofollow noreferrer">Common subtree</a>.</li>
</ul>
<p>(These are formulated as tree problems, but you can generalise them to arbitrary graphs. Then the above formulations are obtained as the special case when you restrict your input to trees.)</p>
<hr />
<p>A more general recipe for generating problems that are hard on trees: Take any NP-hard problem related to <a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node165.html" rel="nofollow noreferrer">supersequences</a>, <a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node166.html" rel="nofollow noreferrer">superstrings</a>, <a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/node167.html" rel="nofollow noreferrer">substrings</a>, etc. Then re-interpret a string as a labelled path graph. Then pose the analogous question for general graphs (subsequence ≈ graph minor, substring ≈ subgraph). And we know that the problem is NP-hard even on trees (and on paths).</p>
<hr />
<p>There are also many problems that are hard on weighted stars, by reduction from the subset-sum problem. A natural example is:</p>
<ul>
<li><em>TSP with two travellers</em>: given an edge-weighted graph <span class="math-container">$G$</span> and a limit <span class="math-container">$W$</span>, can we find two closed walks <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span> in <span class="math-container">$G$</span> such that each walk has total weight at most <span class="math-container">$W$</span>, and each node of <span class="math-container">$G$</span> is covered by at least one walk?</li>
</ul>
<p>Again, it's easy to come up with variations of the theme.</p>

CC BY-SA 2.5
2010-12-09T08:56:02.643Z
Too bad the compendium is not updated anymore.
Anthony Labarre
CC BY-SA 3.0
2016-03-18T09:14:33.370Z
What is a "labelled path graph"?
david
CC BY-SA 4.0
2022-11-08T09:58:18.520Z
@gen fixed now.
Noam Zeilberger
CC BY-SA 4.0
2021-01-30T19:41:26.717Z
The first 4 links in your answer seem to be broken currently. Please could you update the references?
gen
CC BY-SA 4.0
2010-09-12T23:23:33.050Z
2022-11-08T09:57:26.587Z
2022-11-08T09:57:26.587Z
Jukka Suomela
<p>Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set, subgraph isomorphism. Name some natural optimization problems that remain NP-hard on trees.</p>

CC BY-SA 3.0
2011-06-25T04:52:30.357Z
This is not what you asked for, but is worth to mention here: there are some problems that are easy on trees but hard on bounded treewidth. For example, edge-disjoint paths (Nishizeki, Vygen, Zhou '01) and constraint matrix span (McDiarmid, Reed '03).
didest
CC BY-SA 4.0
2018-08-12T10:05:42.210Z
A related problem is to ask for NP-hard decision problems with input only a tree (no other structure - no weights, not even a root vertex). I am afraid if i ask it, it will be marked as a duplicate quesiton.
Cyriac Antony
CC BY-SA 2.5
2010-09-12T23:08:48.463Z
Should be CW, I think. One can generate arbitrarily many contrived examples of such problems. It might be better if people could use voting to rank the answers according to how "natural" the problems are.
Jukka Suomela
CC BY-SA 2.5
2010-09-12T23:15:37.620Z
Jukka, it's debatable if "community wiki" is necessary here. Obviously contrived problems with little relevance will probably get down-voted, anyway.
Ryan Williams
CC BY-SA 2.5
2010-09-12T23:19:45.013Z
I'm also inclined to think that CW is not necessary
Suresh Venkat
CC BY-SA 2.5
2010-09-12T23:19:58.010Z
Not sure if CW is needed. I can't think of any problem off the top of my head. It seems like posters should be rewarded for answering this question.
Robin Kothari
CC BY-SA 2.5
2010-09-12T23:43:34.107Z
Some random Google hits of research papers that show that a problem is NP-hard even if the input is a tree: [capacitated vehicle routing](http://www.jstor.org/pss/171168), [minimum latency problem](http://dx.doi.org/10.1007/3-540-47867-1_17), [call scheduling](http://dx.doi.org/10.1109/HICSS.1997.667220)...
Jukka Suomela
CC BY-SA 2.5
2010-09-13T00:43:59.493Z
@Jukka: Fair enough. I'm neutral on the CW issue.
Robin Kothari
<cc.complexity-theory><np-hardness><tree>
NP-hard problems on trees
Shiva Kintali
# NP-hard problems on trees

(Asked by: username_0 on 2010-09-12)

Several optimization problems that are known to be NP-hard on username_29eral graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set, subgraph isomorphism. Name some natural optimization problems that remain NP-hard on trees.

**Tags:** cc.complexity-theory, np-hardness, tree

> **Comments:**
> **username_3**: Should be CW, I think. One can username_29erate arbitrarily many contrived examples of such problems. It might be better if people could use voting to rank the answers according to how "natural" the problems are.  
> **username_4**: Jukka, it's debatable if "community wiki" is necessary here. Obviously contrived problems with little relevance will probably get down-voted, anyway.  
> **username_5**: I'm also inclined to think that CW is not necessary  
> **username_6**: Not sure if CW is needed. I can't think of any problem off the top of my head. It seems like posters should be rewarded for answering this question.  
> **username_3**: Some random Google hits of research papers that show that a problem is NP-hard even if the input is a tree: [capacitated vehicle routing](http://www.jstor.org/pss/171168), [minimum latency problem](http://dx.doi.org/10.1007/3-540-47867-1_17), [call scheduling](http://dx.doi.org/10.1109/HICSS.1997.667220)...  
> **username_6**: @Jukka: Fair enough. I'm neutral on the CW issue.  
> **username_1**: This is not what you asked for, but is worth to mention here: there are some problems that are easy on trees but hard on bounded treewidth. For example, edge-disjoint paths (Nishizeki, Vyusername_29, Zhou '01) and constraint matrix span (McDiarmid, Reed '03).  
> **username_2**: A related problem is to ask for NP-hard decision problems with input only a tree (no other structure - no weights, not even a root vertex). I am afraid if i ask it, it will be marked as a duplicate quesiton.  

---

## 21 answers

### Answer by username_3 on 2010-09-12. Score: 26 | Accepted answer

You can find "natural" and "well-known" examples of graph problems that are hard even if restricted to trees from [our standard reference](https://www.csc.kth.se/%7Eviggo//wwwcompendium/). Examples:

* [Integral *k*-multicommodity flow](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node121.html),
* [Common embedded subtree](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node60.html),
* [Common subtree](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node168.html).

(These are formulated as tree problems, but you can username_29eralise them to arbitrary graphs. Then the above formulations are obtained as the special case when you restrict your input to trees.)

---

A more username_29eral recipe for username_29erating problems that are hard on trees: Take any NP-hard problem related to [supersequences](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node165.html), [superstrings](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node166.html), [substrings](https://www.csc.kth.se/%7Eviggo/wwwcompendium/node167.html), etc. Then re-interpret a string as a labelled path graph. Then pose the analogous question for username_29eral graphs (subsequence ≈ graph minor, substring ≈ subgraph). And we know that the problem is NP-hard even on trees (and on paths).

---

There are also many problems that are hard on weighted stars, by reduction from the subset-sum problem. A natural example is:

* *TSP with two travellers*: given an edge-weighted graph $G$ and a limit $W$, can we find two closed walks $C\_1$ and $C\_2$ in $G$ such that each walk has total weight at most $W$, and each node of $G$ is covered by at least one walk?

Again, it's easy to come up with variations of the theme.

> **Comments:**
> **username_26**: Too bad the compendium is not updated anymore.  
> **username_27**: What is a "labelled path graph"?  
> **username_29**: The first 4 links in your answer seem to be broken currently. Please could you update the references?  
> **username_28**: @username_29 fixed now.  

---

### Answer by username_7 on 2010-09-13. Score: 38

It is NP-complete to determine whether a tree can be embedded into the two-dimensional integer grid, with the tree vertices placed on distinct grid points and the tree edges placed on grid edges.

See e.g. Gregori, [IPL 1989](http://dx.doi.org/10.1016/0020-0190%2889%2990118-X).

> **Comments:**
> **username_8**: So, this implies the hardness of rectilinear drawing of trees? Is there a degree bound that preserves hardness?  
> **username_7**: Re the degree bound: if there exists a vertex of degree greater than four, then no grid embedding is possible.  
> **username_8**: Thanks David, simple to state yet an interesting problem.  
> **username_2**: Oh, the input tree is also a binary tree. That's great!  

---

### Answer by username_8 on 2010-09-12. Score: 26

One of the hardest problems on trees is minimum bandwidth problem. It is $NP$-hard on trees of maximum degree 3. Also it is NP-hard on circular caterpillar of hair length 1.

References:

Michael R. Garey, Ronald L. Graham, David S.Johnson, and Donald E. Knuth. Complexity results
for bandwidth minimization. SIAM J. Appl. Math., 34(3):477-495, 1978.

Burkhard Monien. The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods, 7(4):505-512, 1986.

W. Unger. The complexity of the approximation of the bandwidth problem. In FOCS, pages
82–91, 1998

> **Comments:**
> **username_9**: The corrected version of Unger's paper is *Hardness results for approximating the bandwidth*, Chandan Dubey, Uriel Feige, and Walter Unger.  

---

### Answer by username_10 on 2010-09-13. Score: 26

Group Steiner problem is a nice example. The input to this problem is an undirected edge-weighted graph $G=(V,E)$ and k groups of vertices $S\_1, S\_2, \ldots, S\_k$. The goal is to find a minimum weight tree that contains at least one vertex from each group. It is easy to see that the Set Cover problem is a special case even when G is a star. Thus the problem is hard to approximate to within a $O(\log n)$ factor unless P=NP. Moreover, it was shown by Halperin and Krauthgamer that the problem is hard to approximate to within an $O(\log^{2-\epsilon} n)$ factor for any fixed $\epsilon > 0$ unless NP has randomized quasi-polynomial time algorithms (see the paper for a precise statement). There is an $O(\log^2 n)$ approximation on trees by Garg, Konjevod and Ravi.

> **Comments:**
> **username_5**: Aaah: the unformatted latex !! it hurts the eyes :)  
> **username_10**: Well, I don't know how to do latex formatting here :). Pointers??  
> **username_5**: just use \$..\$ as usual.  
> **username_5**: ok all fixed now.  

---

### Answer by username_11 on 2012-11-09. Score: 15

The firefighter problem has received a fair amount of attention recently, and is (somewhat surprisingly) [NP-hard on trees of maximum degree 3](http://www.sciencedirect.com/science/article/pii/S0012365X0600776X). It is actually a fairly natural question, described as follows:

A fire breaks out at the root of the tree (or more username_29erally, a specified vertex in a graph). At every step, the firefighter protects one non-burning vertex, after which time the fire spreads to every unprotected neighbour. The process ends when there is no unprotected vertex next to the fire. Is there a strategy for the firefighter in which at most $k$ vertices burn?

[Or a variant, also NP-hard](http://www.sciencedirect.com/science/article/pii/S0012365X09002672): Is there a strategy for the firefighter in which no leaf burns?


---

### Answer by username_12 on 2010-09-13. Score: 15

The unweighted edge multicut problem is the following: Given an undirected graph $G$, a collection of pairs of vertices of $G$, and a positive integer $k$, find if there is a subset $S$ of at most $k$ edges in $G$ whose removal disconnects every pair of vertices in the collection.

This problem is NP-hard (and MAX SNP-hard) on *stars* [[1](https://doi.org/10.1007/BF02523685)].

[[1](https://doi.org/10.1007/BF02523685)] Garg, Vazirani, and Yannakakis, [Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees](https://doi.org/10.1007/BF02523685), Algorithmica, 18(1), pp 3-20, 1997.


---

### Answer by username_13 on 2014-02-15. Score: 8

A harmonious coloring of a simple graph is a proper vertex coloring such that each pair of colors appears together on at most one edge. The Harmonious Chromatic Number of a graph is least number of colors in a harmonious coloring of the graph. This problem of finding Harmonious Chromatic Number was shown to be NP-complete on trees by [Edwards and McDiarmid](http://www.sciencedirect.com/science/article/pii/0166218X9400100R). In fact, they also show that the problem remains NP-complete for trees of radius 3.


---

### Answer by username_14 on 2013-07-07. Score: 8

Given a tree $T$, a partition of $V(T)$ in $k$ levels $\phi: V(T)\to \{1,\ldots, k\}$
(i.e., edges of $T$ connect vertices of neighbouring levels $i$ and $i+1$), and an
integer $K$. Can you permute the vertices inside the levels such that the crossing number
is at most $K$?

This problem is NP-complete, proved by Martin Harrigan and Patrick Healy,
[$k$-Level Crossing Minimization Is NP-Hard for Trees](http://link.springer.com/chapter/10.1007/978-3-642-19094-0_9),
WALCOM 2011, LNCS 6552, pp. 70–76.


---

### Answer by username_5 on 2010-09-12. Score: 8

A problem that one might think would NOT be hard on trees, but is, is the [freeze-tag problem in computational geometry](http://maven.smith.edu/~orourke/TOPP/P35.html): briefly, the problem of scheduling wakeups for robots starting with a single awake 'bot, where makespan is the cost measure.

It's known to be NP-hard on weighted star graphs. However, it's open whether the problem is NP-hard in the plane. One might argue that the NP-hardness comes not from 'tree-ness', but from 'arbitrary metric'-ness, but star graphs only give you a limited space of metrics..


---

### Answer by username_15 on 2013-12-20. Score: 8

Empire colouring is NP-hard for trees.

Let $r$ and $s$ be fixed positive integers, and let $G$ be a graph whose vertex set is
partitioned into blocks (or empires) each containing exactly $r$ vertices. The $(s, r)$-colouring
problem $s$-$\text{COL}\_r$ asks for a colouring of the vertices of the graph $G$ that
uses at most $s$ colours, never assigns the same colour to adjacent vertices in different
empires and, conversely, assigns the same colour to all vertices in the same empire,
disregarding adjacencies.

McGrae and Zito, Empires make cartography hard: The complexity of the empire colouring problem,
[LNCS 6986](http://link.springer.com/chapter/10.1007/978-3-642-25870-1_17) (2011) 179–190,
show that, for trees, $s$-$\text{COL}\_r$ is NP-hard for $s \in \{3,\ldots, 2r − 1\}$
(and solvable in polynomial time for other positive values of $s$.)


---

### Answer by username_16 on 2013-06-12. Score: 7

A flow in a network is confluent if it uses at most one outgoing arc at each node.
NP-hardness of determining a maximum confluent flow in a tree (of diameter 4,
with multiple sinks allowed) is proved in:
[D. Dressler and M. Strehler, Capacitated Confluent Flows: Complexity and Algorithms, LNCS 6078 (2010) 347-358](http://link.springer.com/book/10.1007/978-3-642-13073-1/page/2).


---

### Answer by username_18 on 2014-01-04. Score: 7

The Travelling Repairman Problem (TRP) is known to be NP-hard on weighted trees. In this problem, which is also sometimes called the Minimum Latency Problem, the goal is to find a tour that visits all the vertices of a graph while minimizing the average latency. The latency of a vertex $u$ is the cost of the tour from the origin until the tour visits $u$.

Note that in the related (and more famous) TSP problem, the goal is to minimize the maximum, rather than the average latency. I think the TRP is username_29erally considered a more complicated problem (in fact TSP is in P for tree metrics).

NP-hardness on trees was shown in R.A. Sitters "The Minimum Latency Problem Is NP-Hard for Weighted Trees", ISCO 2002.

> **Comments:**
> **username_19**: That is a nice Problem!  

---

### Answer by username_17 on 2010-09-13. Score: 6

[Maximum leaf-labeled isomorphic subtree](http://dx.doi.org/10.1137/S0097539794269461).
The input is a set $TS$ of leaf-labeled tree (internal nodes are not labeled).
A solution is any tree $T$ such that for each tree $T\_1\in TS$ then $T$ is isomorphic to a subtree of $T\_1$.
The optimal solution is the one that maximizes the number of leaves of $T$.

The problem is NP-hard (actually, it is hard to approximate) only when all input trees have unbounded degree.


---

### Answer by username_8 on 2010-09-18. Score: 5

Graph Motif is NP-Complete problem on trees of maximum degree three:

Fellows, Fertin, Hermelin and Vialette, [Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs](https://doi.org/10.1007/978-3-540-73420-8_31)
Lecture Notes in Computer Science, 2007, Volume 4596/2007, 340-351


---

### Answer by username_8 on 2014-01-03. Score: 5

A graph $G(V, E)$ is 2-splittable if it is possible to partition its edge set into two subsets such that the induced subgraphs are isomorphic. Deciding whether a given graph is 2-splittable is $NP$-complete even if input is restricted to trees.

Formally, the problem is:

**PARTITIONED GRAPH ISOMORPHISM**

INSTANCE: A tree $T = (V,E)$

QUESTION: Is there a partition $\{E1,E2 \}$ of $E$ such that the two forests $T1 = (V,E1)$ and $T2 = (V,E2)$ are isomorphic?

The NP-completeness column cites the unpublished manuscript of Graham and Robinson, "Isomorphic factorization IX: even trees".

D.S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms 3
(1982), 288–300


---

### Answer by username_20 on 2010-09-13. Score: 3

There's a (very username_29eral) problem I had a look at as part of a project: a variant of this problem remains NP-hard even on graphs with two vertices and a single edge, and a different variant is NP-hard on trees. Since the NP-hardness of the first variant obviously doesn't stem from the shape of the graph, the second is probably more interesting.

The problem is the distribution of files on and the routing of downloads in a network (for instance, the intranet of a company). Let $S$ be a set of servers and $C$ be a set of clients. Let $G=(V,E)$ be a graph such that $S \subset V$, $C \subset V$ and $S \cap C = \emptyset$ (so servers and clients are vertices, but there can be vertices that are not servers or clients, think of them as routers). Every $s \in S$ has a capacity (think the size of the harddrives), denoted as $|s|$. Let $F$ be a set of files, where every $f \in F$ has a filesize, denoted as $|f|$. Every $e \in E$ has a throughput, denoted as $t\_e$. We also have a set of requests $R \subseteq C \times F$, where each $(c,f) \in R$ means that client $c$ wants to download file $f$.

The problem is to find for each server $s \in S$ a set of files $A\_s$ such that $\sum\_{f \in A\_s} |f| \leq |s|$ (so to add files to servers without the total filesize exceeding the capacity of the server), and to find a path $P\_r$ in $G$ for every request $r = (c,f) \in R$ such that the path starts at $c$ and ends at a server $s$ with $f \in A\_s$, such that if for some edge $e$, $D\_e$ denotes the set of requests such that for all $r = (c,f) \in D\_e$, $P\_r$ contains $e$, then $\sum\_{(c,f) \in D\_e}|f| \leq t\_e$ (so to route all requests on the graph such that no edge capacity is exceeded).

If you don't require all downloads to be routed but instead try to maximize the sum of the filesizes of the downloads that *are* routed you can easily reduce subset-sum to this problem: you have a single server with vast amounts of space, a single client connected to the server with an edge with a capacity equal to the target value of the subset-sum instance and for every integer in the subset-sum instance you create a file with equal size; the client then wishes to download all these files.

A (much?) more interesting variant for this question is the case that you try to minimize the number of edges whose capacity is exceeded - perhaps the network we are working on models the transatlantic internet cables and replacing a cable is so costly that the difference in cost of upgrade to a factor two faster and an upgrade to a factor three faster is negligible. We also say that the placements of files on the servers are already given and cannot be modified, so we look solely at the routing issues.

The set-cover problem can easily be reduced to this variant. We are given a set $U$ called the universe and several subsets $S \subseteq P(U)$ of this universe. We are asked to pick the smallest amount of subsets such that their union equals the universe. For every $u \in U$ we create a file of size 1. We have a single client that wants to download all these files.

For every subset $s \in S$, we create a 'cluster' of servers: a cluster consists of a single vertex (a router) connected to a number of servers such that the servers are only connected to the router. For every $u \in s$ we add a single server to the cluster with the file on it corresponding to $u$. These clusters are then connected to the client with an edge of capacity 1 (so each edge connects the client with the router for the cluster). Furthermore, for every server cluster we add one more server to that cluster hosting a single new file (unique to that cluster) of size 1. All these files (so, in addition to the files corresponding to elements of the universe) are requested by the client.

The idea is that the client needs the files that are unique for all the server clusters, so the edges connecting the client to the server clusters are already at the limit of their capacities (their capacities are 1, the files have size 1). If the client downloads any elements of the universe from any cluster, the edge connecting to that cluster becomes overloaded. Since we only require to minimize the *number* of overloads (and not by how much we exceed the capacities), the client can download the rest of the elements of the universe hosted at that server cluster (so the rest of the elements of the corresponding subset) without penalty. This therefore corresponds to the subset being chosen. The client wants to download all the files in the universe once, so the universe will indeed be covered, and to minimize the number of edges that are overloaded we need to minimize the number of subsets chosen.

Note that the above construction yields a tree graph, so it's an example of an NP-hard problem on trees.


---

### Answer by username_21 on 2012-11-09. Score: 3

The Unsplittable Flow Problem. In fact UFP is hard even on a single edge (Knapsack).


---

### Answer by username_13 on 2014-02-20. Score: 3

Somehow i missed the Achromatic Number problem in the last answer, but this is one of the most natural problems i know of, which are NP-complete on trees.

A complete coloring of a graph is a proper coloring such that there is an edge between every pair of color classes. The coloring can be stated in contrast to Harmonious Coloring, as a proper coloring such that each pair of colors appears on *at least* one edge. Also, it can be stated as a complete (or full) homomorphism to a clique. The Achromatic Number problem is a *maximization* problem, where we look for largest number of color classes in a complete coloring of the graph.

Yannakakis and Gravil proved this problem to be [NP-hard on complement of Bipartite Graphs](http://epubs.siam.org/doi/abs/10.1137/0138030). Cairnie and Edwards extended that result and showed that the problem is [NP-complete on trees](http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291097-0118%28199711%2926:3%3C129%3a%3aAID-JGT3%3E3.0.CO;2-T/abstract).

A lot of work has been done on this problem in the field of Approximation Algorithms [[3](http://www.researchgate.net/publication/2942749_Approximation_Algorithms_for_the_Achromatic_Number),[4](http://www.researchgate.net/publication/2942749_Approximation_Algorithms_for_the_Achromatic_Number),[5](http://www.sciencedirect.com/science/article/pii/0012365X81901643)].


---

### Answer by username_22 on 2016-03-17. Score: 2

k-Balanced Partition Problem on graphs, in which one has to partition the $n$ vertices into $k$ connected components of size at most $\lceil\frac{n}{k}\rceil$ each and at the same time minimize the total cost of edges connecting vertices in different sets, called the cut cost.
This problem is actually APX-hard even on unweighted trees of constant maximum degree[[1](http://lucafoschini.com/papers/Balanced_Algorithmica.pdf)].


---

### Answer by username_2 on 2024-12-14. Score: 0

*Packing coloring* in NP-complete for trees, as proved in Fiala and Golovach, Complexity of the packing coloring problem for trees (2010). This problem was introduced under the name broadcast coloring by Goddard et al. motivated by an application in broadcast networks.

Packing $k$-coloring is a partitioning of the vertex set of a graph into $k$ disjoints sets with the property that vertices in the $i$th set have pairwise distance greater than $i$.

*Packing Coloring*  
Instance: A graph $G$ and a positive integer $k$.  
Question: Does $G$ allow a packing $k$-coloring?

The packing chromatic number of trees of maximum degree three is at most 7, while it is unbounded for trees of maximum degree four. It is unknown to me whether *Packing coloring* is NP-complete for trees of maximum degree four.


---

### Answer by username_23 on 2016-03-17. Score: -1

Is Circuit SAT on trees NPC?. Tree inner vertices are labeled as OR/AND gates. Leaves are inputs. Determine if there is a satisfying set of inputs for the circuit to evaluate to True.

At first glance it seems you can solve bottom up, but constraints get nasty as you move up the tree and OR gates suddenly need one of the other $2^k - 1$ assignments.

> **Comments:**
> **username_24**: Umm, circuits that are trees have a name: formulas. Formula SAT is of course NP-complete, as 3-SAT or even full CNF-SAT are its special cases.  
> **username_23**: Formulas without repeated variables.  
> **username_24**: How so? *All* formulas are trees. If you want to restrict multiple occurrences of variables, that’s an additional constraint. (I also assume that when you write “inputs”, you really mean “literals”, as Circuit SAT with only AND, OR, and positive literals is trivially polynomial-time to begin with.)  
> **username_23**: a+b+c+a   (Variable a is repeated twice, thus DAG not tree).  
> **username_24**: Certainly not under the standard terminology. The formulas $((a+b)+c)+d$ and $((a+b)+c)+a$ have the same underlying tree, only with different labels at one of the nodes. A tree stays a tree no matter how are its leaves relabelled.  
> **username_25**: Emil is right. A formula like $(p \land q) \lor p$ is a tree. Fan-out does not apply to input gates in circuits. With your definition that a variable cannot appear both positively and negatively therefore the formula is trivially satisfiable.  
> **username_23**: Implicit DAG in your example. Either you make the $p$ value form a diamond where it is referenced from two gates, or you cheat and and have an implicit constraint in the formula that both $p$ leaves must be assigned the same value.  Allowing constraints that certain inputs must be equivalent seems to unnecessarily complicate a nice toy problem.  
> **username_25**: It is not a toy problem. This is the standard terminology, when when we say a circuit is a tree it does not mean variables appear only once. In any case and independent of what we call it the problem you proposing is trivial as I wrote.  

---

