31:
615:
34:
A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the tree. Each tree node lists at most three vertices, so
1366:
is a constant then the whole calculation takes constant time per edge or node. The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these
1304:
1175:
1386:
the treewidth, constructing a tree decomposition with this approximate width, and then a second step that performs dynamic programming in the approximate tree decomposition to compute the exact value of the treewidth.
652:. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one. Treewidth may also be defined from other structures than tree decompositions, including
1367:
stored values starting from this largest value. Thus, in graphs of bounded treewidth, the maximum independent set problem may be solved in linear time. Similar algorithms apply to many other graph problems.
598:
411:
1382:
in graphs of bounded treewidth. It also plays a key role in algorithms for computing the treewidth and constructing tree decompositions: typically, such algorithms have a first step that
939:
1024:
148:
Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each tree node as the set of vertices associated with it. Thus, given a graph
518:
794:
862:
1342:
705:
At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial
1412:
417:
The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node.
1040:
713:, a parameter related to treewidth. Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are
1181:
1403: – Two kinds of structures that can be used as an alternative to tree decomposition in defining the treewidth of a graph.
1712:
1623:
1722:
Gottlob, Georg; Lee, Stephanie Tien; Valiant, Gregory; Valiant, Paul (2012), "Size and treewidth bounds for conjunctive queries",
1704:
1797:
1788:
102:
424:
is called a path decomposition, and the width parameter derived from these special types of tree decompositions is known as
1840:
1830:
732:. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node
1792:
106:
48:
1835:
523:
363:
1415: – Tree Decomposition is used in Decomposition Method for solving constraint satisfaction problem.
895:
134:
974:
1383:
1375:
725:
79:
1675:
1396:
657:
1562:
Arnborg, S.; Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial
260:. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
462:
1406:
1400:
763:
661:
87:
1680:
825:
1409: – A closely related structure whose width is within a constant factor of treewidth.
718:
706:
52:
1698:
687:
tree decomposition constructed for them, in linear time. The time dependence of this algorithm on
1776:
1724:
1663:
1633:
1379:
138:
83:
75:
1708:
1619:
1593:; Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs",
1806:
1768:
1733:
1685:
1649:
1641:
1602:
1575:
1550:
1371:
1312:
19:
This article is about tree structure of graphs. For decomposition of graphs into trees, see
1745:
1741:
714:
1640:, Lecture Notes in Computer Science, vol. 317, Springer-Verlag, pp. 105–118,
1666:(1996), "A linear time algorithm for finding tree-decompositions of small treewidth",
1824:
1811:
1780:
1606:
1590:
1580:
1534:
653:
142:
1752:
614:
94:
40:
20:
30:
1170:{\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)}
721:
for graphs of bounded treewidth, using the tree-decompositions of these graphs.
59:
of the graph and speed up solving certain computational problems on the graph.
1689:
1645:
421:
1737:
1299:{\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}
634:
609:
425:
56:
24:
121:
Intuitively, a tree decomposition represents the vertices of a given graph
1638:
Proc. 15th
International Colloquium on Automata, Languages and Programming
1772:
230:. That is, each graph vertex is associated with at least one tree node.
1654:
1554:
129:
are adjacent only when the corresponding subtrees intersect. Thus,
1537:; Proskurowski, A. (1987), "Complexity of finding embeddings in a
613:
29:
1636:(1988), "Dynamic programming on graphs with bounded treewidth",
648:
is the minimum width among all possible tree decompositions of
93:
The concept of tree decomposition was originally introduced by
1484:
1431:
626:
of a tree decomposition is the size of its largest set
420:
A tree decomposition in which the underlying tree is a
125:
as subtrees of a tree, in such a way that vertices in
1315:
1184:
1043:
977:
898:
828:
766:
667:
It is NP-complete to determine whether a given graph
526:
465:
366:
113:) and has since been studied by many other authors.
1508:
1362:for which we need to calculate these values, so if
724:As an example, consider the problem of finding the
618:
Two different tree-decompositions of the same graph
306:as well. That is, the nodes associated with vertex
1336:
1298:
1169:
1018:
960:denote the size of the largest independent subset
933:
856:
811:denote the size of the largest independent subset
788:
717:for arbitrary graphs may be solved efficiently by
592:
512:
405:
141:of the subtrees. The full intersection graph is a
679:is any fixed constant, the graphs with treewidth
1543:SIAM Journal on Matrix Analysis and Applications
1213:
110:
74:. They play an important role in problems like
1795:(1984), "Graph minors III: Planar tree-width",
1496:
1614:Bertelé, Umberto; Brioschi, Francesco (1972),
1512:
593:{\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}
406:{\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}
1370:This dynamic programming approach is used in
1034:values by a bottom-up traversal of the tree:
8:
23:. For decomposition of trees in nature, see
1516:
1485:Arnborg, Corneil & Proskurowski (1987)
1472:
314:. This is also known as coherence, or the
21:Graph theory § Decomposition problems
1810:
1679:
1653:
1579:
1314:
1263:
1234:
1216:
1183:
1157:
1151:
1136:
1112:
1085:
1073:
1065:
1042:
1001:
988:
976:
934:{\displaystyle S\subset X_{i}\cap X_{j},}
922:
909:
897:
864:Similarly, for an adjacent pair of nodes
839:
827:
777:
765:
579:
573:
560:
551:
525:
493:
487:
478:
464:
397:
384:
371:
365:
288:of the tree in the (unique) path between
196:is a family of subsets (sometimes called
1354:At each node or edge, there are at most
1019:{\displaystyle I\cap X_{i}\cap X_{j}=S.}
318:. It can be stated equivalently that if
1455:
1443:
1424:
885:farther from the root of the tree than
671:has treewidth at most a given variable
215:, satisfying the following properties:
35:the width of this decomposition is two.
208:is a tree whose nodes are the subsets
1468:
1466:
1464:
98:
7:
1309:where the sum in the calculation of
62:Tree decompositions are also called
709:as long as the graph had a bounded
1217:
513:{\displaystyle i\in I:|X_{i}|=k+1}
14:
1509:Arnborg & Proskurowski (1989)
163:, a tree decomposition is a pair
245:in the graph, there is a subset
101:). Later it was rediscovered by
1798:Journal of Combinatorial Theory
789:{\displaystyle S\subset X_{i},}
739:of the tree decomposition, let
683:can be recognized, and a width
55:that can be used to define the
1513:Bern, Lawler & Wong (1987)
1331:
1319:
1293:
1276:
1206:
1188:
1158:
1137:
1130:
1099:
1074:
1066:
1059:
1047:
857:{\displaystyle I\cap X_{i}=S.}
691:is an exponential function of
580:
552:
539:
527:
494:
479:
16:Mapping of a graph into a tree
1:
1616:Nonserial Dynamic Programming
1497:Bertelé & Brioschi (1972)
1344:is over the children of node
316:running intersection property
1812:10.1016/0095-8956(84)90013-3
1607:10.1016/0196-6774(87)90039-3
1581:10.1016/0166-218X(89)90031-0
1568:Discrete Applied Mathematics
310:form a connected subset of
1857:
1697:Diestel, Reinhard (2005),
607:
18:
1690:10.1137/S0097539793251219
1668:SIAM Journal on Computing
1646:10.1007/3-540-19488-6_110
892:, and an independent set
760:. For an independent set
746:be the union of the sets
1759:-functions for graphs",
728:in a graph of treewidth
1738:10.1145/2220357.2220363
1376:junction tree algorithm
1026:We may calculate these
726:maximum independent set
80:constraint satisfaction
76:probabilistic inference
1338:
1337:{\displaystyle A(S,i)}
1300:
1171:
1020:
935:
858:
790:
619:
594:
514:
407:
277:both contain a vertex
219:The union of all sets
36:
1595:Journal of Algorithms
1432:Gottlob et al. (2012)
1339:
1301:
1172:
1021:
936:
859:
791:
617:
595:
515:
431:A tree decomposition
408:
33:
1841:Graph theory objects
1831:Trees (graph theory)
1413:Decomposition Method
1407:Branch-decomposition
1313:
1182:
1041:
975:
896:
826:
764:
524:
463:
364:
346:is on the path from
88:matrix decomposition
1761:Journal of Geometry
1732:(3): A16:1–A16:35,
1664:Bodlaender, Hans L.
1634:Bodlaender, Hans L.
719:dynamic programming
707:dynamic programming
701:Dynamic programming
252:that contains both
1836:Graph minor theory
1773:10.1007/BF01917434
1725:Journal of the ACM
1618:, Academic Press,
1380:belief propagation
1334:
1296:
1272:
1167:
1090:
1016:
931:
854:
786:
620:
590:
510:
403:
139:intersection graph
103:Neil Robertson
84:query optimization
47:is a mapping of a
45:tree decomposition
37:
1517:Bodlaender (1988)
1473:Bodlaender (1996)
1270:
1212:
1081:
281:, then all nodes
1848:
1815:
1814:
1793:Seymour, Paul D.
1783:
1767:(1–2): 171–186,
1748:
1717:
1703:(3rd ed.),
1692:
1683:
1674:(6): 1305–1317,
1658:
1657:
1628:
1609:
1584:
1583:
1557:
1520:
1506:
1500:
1494:
1488:
1482:
1476:
1470:
1459:
1453:
1447:
1441:
1435:
1429:
1372:machine learning
1365:
1361:
1357:
1350:
1343:
1341:
1340:
1335:
1305:
1303:
1302:
1297:
1286:
1271:
1269:
1268:
1267:
1255:
1240:
1239:
1238:
1226:
1176:
1174:
1173:
1168:
1166:
1162:
1161:
1156:
1155:
1140:
1117:
1116:
1089:
1077:
1069:
1033:
1029:
1025:
1023:
1022:
1017:
1006:
1005:
993:
992:
970:
963:
959:
940:
938:
937:
932:
927:
926:
914:
913:
891:
884:
877:
870:
863:
861:
860:
855:
844:
843:
821:
814:
810:
795:
793:
792:
787:
782:
781:
759:
753:descending from
752:
745:
738:
731:
696:
690:
686:
682:
678:
675:. However, when
674:
670:
651:
647:
643:
632:
599:
597:
596:
591:
583:
578:
577:
565:
564:
555:
519:
517:
516:
511:
497:
492:
491:
482:
454:
450:
412:
410:
409:
404:
402:
401:
389:
388:
376:
375:
359:
352:
345:
338:
331:
324:
313:
309:
305:
301:
294:
287:
280:
276:
269:
259:
255:
251:
244:
229:
225:
214:
207:
203:
195:
174:
162:
132:
128:
124:
95:Rudolf Halin
1856:
1855:
1851:
1850:
1849:
1847:
1846:
1845:
1821:
1820:
1819:
1789:Robertson, Neil
1787:
1751:
1721:
1715:
1696:
1681:10.1.1.113.4539
1662:
1632:
1626:
1613:
1588:
1561:
1555:10.1137/0608024
1532:
1528:
1523:
1507:
1503:
1495:
1491:
1483:
1479:
1471:
1462:
1454:
1450:
1442:
1438:
1430:
1426:
1422:
1393:
1363:
1359:
1355:
1349:
1345:
1311:
1310:
1279:
1259:
1248:
1241:
1230:
1219:
1218:
1180:
1179:
1147:
1108:
1095:
1091:
1039:
1038:
1031:
1027:
997:
984:
973:
972:
969:
965:
961:
942:
918:
905:
894:
893:
890:
886:
883:
879:
876:
872:
869:
865:
835:
824:
823:
820:
816:
812:
797:
773:
762:
761:
758:
754:
751:
747:
744:
740:
737:
733:
729:
703:
692:
688:
684:
680:
676:
672:
668:
649:
645:
637:
633:minus one. The
631:
627:
612:
606:
569:
556:
522:
521:
483:
461:
460:
452:
432:
393:
380:
367:
362:
361:
358:
354:
351:
347:
344:
340:
339:are nodes, and
337:
333:
330:
326:
323:
319:
311:
307:
303:
300:
296:
293:
289:
286:
282:
278:
275:
271:
268:
264:
257:
253:
250:
246:
234:
233:For every edge
227:
224:
220:
213:
209:
205:
201:
192:
186:
176:
164:
149:
130:
126:
122:
119:
28:
17:
12:
11:
5:
1854:
1852:
1844:
1843:
1838:
1833:
1823:
1822:
1818:
1817:
1785:
1749:
1719:
1713:
1694:
1660:
1630:
1624:
1611:
1601:(2): 216–235,
1586:
1559:
1549:(2): 277–284,
1529:
1527:
1524:
1522:
1521:
1501:
1489:
1477:
1460:
1456:Diestel (2005)
1448:
1444:Diestel (2005)
1436:
1423:
1421:
1418:
1417:
1416:
1410:
1404:
1392:
1389:
1347:
1333:
1330:
1327:
1324:
1321:
1318:
1307:
1306:
1295:
1292:
1289:
1285:
1282:
1278:
1275:
1266:
1262:
1258:
1254:
1251:
1247:
1244:
1237:
1233:
1229:
1225:
1222:
1215:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1177:
1165:
1160:
1154:
1150:
1146:
1143:
1139:
1135:
1132:
1129:
1126:
1123:
1120:
1115:
1111:
1107:
1104:
1101:
1098:
1094:
1088:
1084:
1080:
1076:
1072:
1068:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1015:
1012:
1009:
1004:
1000:
996:
991:
987:
983:
980:
967:
930:
925:
921:
917:
912:
908:
904:
901:
888:
881:
874:
867:
853:
850:
847:
842:
838:
834:
831:
818:
785:
780:
776:
772:
769:
756:
749:
742:
735:
702:
699:
654:chordal graphs
629:
608:Main article:
605:
602:
589:
586:
582:
576:
572:
568:
563:
559:
554:
550:
547:
544:
541:
538:
535:
532:
529:
520:, and for all
509:
506:
503:
500:
496:
490:
486:
481:
477:
474:
471:
468:
415:
414:
400:
396:
392:
387:
383:
379:
374:
370:
356:
349:
342:
335:
328:
321:
298:
291:
284:
273:
266:
261:
248:
231:
222:
211:
190:
184:
118:
115:
64:junction trees
15:
13:
10:
9:
6:
4:
3:
2:
1853:
1842:
1839:
1837:
1834:
1832:
1829:
1828:
1826:
1813:
1808:
1804:
1800:
1799:
1794:
1790:
1786:
1782:
1778:
1774:
1770:
1766:
1762:
1758:
1754:
1753:Halin, Rudolf
1750:
1747:
1743:
1739:
1735:
1731:
1727:
1726:
1720:
1716:
1714:3-540-26182-6
1710:
1706:
1702:
1701:
1695:
1691:
1687:
1682:
1677:
1673:
1669:
1665:
1661:
1656:
1651:
1647:
1643:
1639:
1635:
1631:
1627:
1625:0-12-093450-7
1621:
1617:
1612:
1608:
1604:
1600:
1596:
1592:
1591:Lawler, E. L.
1589:Bern, M. W.;
1587:
1582:
1577:
1573:
1569:
1565:
1560:
1556:
1552:
1548:
1544:
1540:
1536:
1533:Arnborg, S.;
1531:
1530:
1525:
1518:
1514:
1510:
1505:
1502:
1498:
1493:
1490:
1486:
1481:
1478:
1474:
1469:
1467:
1465:
1461:
1457:
1452:
1449:
1445:
1440:
1437:
1433:
1428:
1425:
1419:
1414:
1411:
1408:
1405:
1402:
1398:
1395:
1394:
1390:
1388:
1385:
1381:
1377:
1373:
1368:
1352:
1328:
1325:
1322:
1316:
1290:
1287:
1283:
1280:
1273:
1264:
1260:
1256:
1252:
1249:
1245:
1242:
1235:
1231:
1227:
1223:
1220:
1209:
1203:
1200:
1197:
1194:
1191:
1185:
1178:
1163:
1152:
1148:
1144:
1141:
1133:
1127:
1124:
1121:
1118:
1113:
1109:
1105:
1102:
1096:
1092:
1086:
1082:
1078:
1070:
1062:
1056:
1053:
1050:
1044:
1037:
1036:
1035:
1013:
1010:
1007:
1002:
998:
994:
989:
985:
981:
978:
957:
953:
949:
945:
928:
923:
919:
915:
910:
906:
902:
899:
851:
848:
845:
840:
836:
832:
829:
808:
804:
800:
783:
778:
774:
770:
767:
727:
722:
720:
716:
712:
708:
700:
698:
695:
665:
663:
659:
655:
641:
636:
625:
616:
611:
603:
601:
587:
584:
574:
570:
566:
561:
557:
548:
545:
542:
536:
533:
530:
507:
504:
501:
498:
488:
484:
475:
472:
469:
466:
459:, if for all
458:
451:of treewidth
448:
444:
440:
436:
429:
427:
423:
418:
398:
394:
390:
385:
381:
377:
372:
368:
317:
262:
242:
238:
232:
218:
217:
216:
199:
193:
183:
179:
172:
168:
160:
156:
152:
146:
144:
143:chordal graph
140:
136:
116:
114:
112:
108:
105: and
104:
100:
96:
91:
89:
85:
81:
77:
73:
69:
65:
60:
58:
54:
50:
46:
42:
32:
26:
22:
1805:(1): 49–64,
1802:
1801:, Series B,
1796:
1764:
1760:
1756:
1729:
1723:
1700:Graph Theory
1699:
1671:
1667:
1637:
1615:
1598:
1594:
1574:(1): 11–24,
1571:
1567:
1563:
1546:
1542:
1538:
1504:
1492:
1480:
1458:section 12.3
1451:
1439:
1427:
1384:approximates
1369:
1353:
1308:
955:
951:
947:
943:
806:
802:
798:
723:
710:
704:
693:
666:
639:
623:
621:
456:
446:
442:
438:
434:
430:
419:
416:
315:
240:
236:
197:
188:
181:
177:
170:
166:
158:
154:
150:
147:
120:
107:Paul Seymour
92:
71:
68:clique trees
67:
63:
61:
44:
41:graph theory
38:
1535:Corneil, D.
715:NP-complete
644:of a graph
1825:Categories
1655:1874/16258
1526:References
1446:pp.354–355
971:such that
822:such that
422:path graph
117:Definition
72:join trees
1781:120256194
1755:(1976), "
1676:CiteSeerX
1566:-trees",
1257:∩
1228:⊂
1145:∩
1134:−
1106:∩
1083:∑
995:∩
982:∩
916:∩
903:⊂
833:∩
771:⊂
711:dimension
635:treewidth
610:Treewidth
604:Treewidth
567:∩
543:∈
470:∈
426:pathwidth
391:⊆
378:∩
57:treewidth
25:Nurse log
1705:Springer
1541:-tree",
1397:Brambles
1391:See also
1374:via the
1284:′
1253:′
1224:′
658:brambles
302:contain
175:, where
135:subgraph
133:forms a
1746:2946220
878:, with
360:, then
226:equals
137:of the
109: (
97: (
51:into a
1779:
1744:
1711:
1678:
1622:
1401:havens
662:havens
660:, and
457:smooth
204:, and
86:, and
1777:S2CID
1420:Notes
1358:sets
624:width
200:) of
187:, …,
70:, or
49:graph
1709:ISBN
1620:ISBN
1399:and
1378:for
1030:and
941:let
871:and
796:let
622:The
332:and
295:and
270:and
256:and
198:bags
111:1984
99:1976
53:tree
43:, a
1807:doi
1769:doi
1734:doi
1686:doi
1650:hdl
1642:doi
1603:doi
1576:doi
1551:doi
1214:max
964:of
815:of
638:tw(
455:is
441:= (
353:to
263:If
180:= {
153:= (
39:In
1827::
1803:36
1791:;
1775:,
1763:,
1742:MR
1740:,
1730:59
1728:,
1707:,
1684:,
1672:25
1670:,
1648:,
1597:,
1572:23
1570:,
1545:,
1515:;
1511:;
1463:^
1351:.
697:.
664:.
656:,
600:.
449:))
445:,
437:,
428:.
325:,
239:,
169:,
157:,
145:.
90:.
82:,
78:,
66:,
1816:.
1809::
1784:.
1771::
1765:8
1757:S
1736::
1718:.
1693:.
1688::
1659:.
1652::
1644::
1629:.
1610:.
1605::
1599:8
1585:.
1578::
1564:k
1558:.
1553::
1547:8
1539:k
1519:.
1499:.
1487:.
1475:.
1434:.
1364:k
1360:S
1356:2
1348:i
1346:X
1332:)
1329:i
1326:,
1323:S
1320:(
1317:A
1294:)
1291:i
1288:,
1281:S
1277:(
1274:A
1265:j
1261:X
1250:S
1246:=
1243:S
1236:i
1232:X
1221:S
1210:=
1207:)
1204:j
1201:,
1198:i
1195:,
1192:S
1189:(
1186:B
1164:)
1159:|
1153:j
1149:X
1142:S
1138:|
1131:)
1128:i
1125:,
1122:j
1119:,
1114:j
1110:X
1103:S
1100:(
1097:B
1093:(
1087:j
1079:+
1075:|
1071:S
1067:|
1063:=
1060:)
1057:i
1054:,
1051:S
1048:(
1045:A
1032:B
1028:A
1014:.
1011:S
1008:=
1003:j
999:X
990:i
986:X
979:I
968:i
966:D
962:I
958:)
956:j
954:,
952:i
950:,
948:S
946:(
944:B
929:,
924:j
920:X
911:i
907:X
900:S
889:j
887:X
882:i
880:X
875:j
873:X
868:i
866:X
852:.
849:S
846:=
841:i
837:X
830:I
819:i
817:D
813:I
809:)
807:i
805:,
803:S
801:(
799:A
784:,
779:i
775:X
768:S
757:i
755:X
750:j
748:X
743:i
741:D
736:i
734:X
730:k
694:k
689:k
685:k
681:k
677:k
673:k
669:G
650:G
646:G
642:)
640:G
630:i
628:X
588:k
585:=
581:|
575:j
571:X
562:i
558:X
553:|
549::
546:F
540:)
537:j
534:,
531:i
528:(
508:1
505:+
502:k
499:=
495:|
489:i
485:X
480:|
476::
473:I
467:i
453:k
447:F
443:I
439:T
435:X
433:(
413:.
399:k
395:X
386:j
382:X
373:i
369:X
357:j
355:X
350:i
348:X
343:k
341:X
336:k
334:X
329:j
327:X
322:i
320:X
312:T
308:v
304:v
299:j
297:X
292:i
290:X
285:k
283:X
279:v
274:j
272:X
267:i
265:X
258:w
254:v
249:i
247:X
243:)
241:w
237:v
235:(
228:V
223:i
221:X
212:i
210:X
206:T
202:V
194:}
191:n
189:X
185:1
182:X
178:X
173:)
171:T
167:X
165:(
161:)
159:E
155:V
151:G
131:G
127:G
123:G
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
