45:
The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution. This technique has given PTASs for the following problems:
979:-outerplanar graphs. Baker's technique can be interpreted as covering the given planar graphs with subgraphs of this type, finding the solution to each subgraph using dynamic programming, and gluing the solutions together.
1134:
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi (2011), "Contraction decomposition in J-minor-free graphs and algorithmic applications", in
Fortnow, Lance; Vadhan, Salil P. (eds.),
484:
689:
794:
379:
425:
934:
902:
830:
723:
635:
603:
571:
236:
308:
859:
531:
183:
977:
955:
504:
276:
256:
203:
163:
143:
1182:; Hajiaghayi, M.; Nishimura, N.; Ragde, P.; Thilikos, D. (2004), "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.",
1095:
Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: Decomposition, approximation, and coloring",
1098:
46th Annual IEEE Symposium on
Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, Proceedings
1057:
Automata, Languages and
Programming, 15th International Colloquium, ICALP '88, Tampere, Finland, July 11–15, 1988, Proceedings
1086:
1293:
25:
430:
639:
1363:
1162:
1117:
1060:
728:
313:
101:, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the
114:
17:
1137:
Proceedings of the 43rd ACM Symposium on Theory of
Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011
386:
1055:(1988), "Dynamic programming on graphs with bounded treewidth", in Lepistö, Timo; Salomaa, Arto (eds.),
1353:
93:) generalizes and greatly expands the applicability of Baker's technique for a vast set of problems on
993:(1983), "Approximation algorithms for NP-complete problems on planar graphs (preliminary version)",
907:
875:
801:
694:
608:
576:
538:
207:
995:
24th Annual
Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7–9 November 1983
280:
51:
1358:
837:
509:
168:
59:
1096:
1327:
1273:
1037:
55:
47:
8:
937:
869:
78:
63:
1331:
1289:
1277:
1235:
1217:
1168:
1123:
1052:
1041:
1014:
962:
940:
489:
261:
241:
188:
148:
128:
38:
1158:
1113:
1082:
1172:
1127:
113:
The example that we will use to demonstrate Baker's technique is the maximum weight
1335:
1313:
1305:
1281:
1259:
1239:
1227:
1191:
1148:
1140:
1105:
1072:
1064:
1045:
1023:
998:
70:
1323:
1269:
1033:
1247:
1205:
1196:
102:
1309:
1068:
1012:(1994), "Approximation algorithms for NP-complete problems on planar graphs",
1347:
1144:
1179:
1009:
990:
94:
74:
33:
29:
1231:
1028:
1109:
98:
1153:
1002:
1264:
1222:
1318:
1250:(1999), "Subgraph isomorphism in planar graphs and related problems",
1077:
959:. Many NP-complete problems can be solved with dynamic programming on
872:
is used when we compute the maximum-weight independent set for each
1208:(2000), "Diameter and treewidth in minor-closed graph families.",
36:, who announced it in a 1983 conference and published it in the
1178:
1294:"Algorithms for graphs embeddable with few crossings per edge"
1133:
1094:
90:
86:
834:
Notice that the above algorithm is feasible because each
965:
943:
910:
878:
840:
804:
731:
697:
642:
611:
579:
541:
512:
492:
433:
389:
316:
283:
264:
244:
210:
191:
171:
151:
131:
479:{\displaystyle G_{1}^{\ell },G_{2}^{\ell },\ldots ,}
1287:
971:
949:
928:
896:
853:
824:
788:
717:
683:
629:
597:
565:
525:
498:
478:
419:
373:
302:
270:
250:
230:
197:
177:
157:
137:
1345:
684:{\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell }}
789:{\displaystyle \{S^{0},S^{1},\ldots ,S^{k-1}\}}
374:{\displaystyle \{V_{0},V_{1},\ldots ,V_{k-1}\}}
91:Demaine, Hajiaghayi & Kawarabayashi (2011)
87:Demaine, Hajiaghayi & Kawarabayashi (2005)
66:, maximum triangle matching, and many others.
1063:, vol. 317, Springer, pp. 105–118,
1252:Journal of Graph Algorithms and Applications
783:
732:
368:
317:
1104:, IEEE Computer Society, pp. 637–646,
997:, IEEE Computer Society, pp. 265–273,
861:is the union of disjoint independent sets.
1051:
904:. This dynamic program works because each
81:, and Dimitrios Thilikos and its offshoot
1317:
1263:
1221:
1195:
1152:
1076:
1027:
238:find the breadth-first search levels for
1246:
1204:
725:be the solution of maximum weight among
605:, the maximum-weight independent set of
108:
1346:
864:
1008:
989:
26:polynomial-time approximation schemes
420:{\displaystyle \ell =0,\ldots ,k-1}
292:
13:
14:
1375:
1061:Lecture Notes in Computer Science
185:) Choose an arbitrary vertex
285:
296:
286:
99:graphs excluding a fixed minor
1:
982:
929:{\displaystyle G_{i}^{\ell }}
897:{\displaystyle G_{i}^{\ell }}
825:{\displaystyle S^{\ell ^{*}}}
718:{\displaystyle S^{\ell ^{*}}}
630:{\displaystyle G_{i}^{\ell }}
598:{\displaystyle S_{i}^{\ell }}
566:{\displaystyle i=1,2,\ldots }
231:{\displaystyle k=1/\epsilon }
120:
18:theoretical computer science
7:
303:{\displaystyle {\pmod {k}}}
10:
1380:
1197:10.1016/j.jcss.2003.12.001
83:simplifying decompositions
24:is a method for designing
1310:10.1007/s00453-007-0010-x
1139:, ACM, pp. 441–450,
1069:10.1007/3-540-19488-6_110
854:{\displaystyle S^{\ell }}
526:{\displaystyle V_{\ell }}
178:{\displaystyle \epsilon }
1364:Approximation algorithms
28:(PTASs) for problems on
1145:10.1145/1993636.1993696
71:bidimensionality theory
52:maximum independent set
1288:Grigoriev, Alexander;
973:
951:
930:
898:
855:
826:
790:
719:
685:
631:
599:
567:
527:
500:
480:
421:
375:
304:
272:
252:
232:
199:
179:
159:
139:
60:minimum dominating set
1232:10.1007/s004530010020
1184:J. Comput. Syst. Sci.
1029:10.1145/174644.174650
974:
952:
931:
899:
856:
827:
791:
720:
686:
632:
600:
568:
528:
501:
481:
422:
376:
305:
273:
253:
233:
200:
180:
160:
140:
1110:10.1109/SFCS.2005.14
963:
941:
908:
876:
838:
802:
729:
695:
640:
609:
577:
539:
510:
490:
431:
427:find the components
387:
314:
281:
262:
242:
208:
189:
169:
149:
129:
109:Example of technique
97:and more generally
56:minimum vertex cover
48:subgraph isomorphism
32:. It is named after
1290:Bodlaender, Hans L.
1053:Bodlaender, Hans L.
1003:10.1109/SFCS.1983.7
925:
893:
870:Dynamic programming
865:Dynamic programming
680:
626:
594:
466:
448:
64:edge dominating set
1265:10.7155/jgaa.00014
1015:Journal of the ACM
969:
957:-outerplanar graph
947:
926:
911:
894:
879:
851:
822:
786:
715:
681:
666:
627:
612:
595:
580:
563:
523:
496:
476:
452:
434:
417:
371:
300:
268:
248:
228:
195:
175:
155:
135:
39:Journal of the ACM
1354:1983 in computing
1088:978-3-540-19488-0
972:{\displaystyle k}
950:{\displaystyle k}
499:{\displaystyle G}
271:{\displaystyle r}
251:{\displaystyle G}
198:{\displaystyle r}
158:{\displaystyle w}
138:{\displaystyle G}
22:Baker's technique
1371:
1338:
1321:
1284:
1267:
1242:
1225:
1200:
1199:
1175:
1156:
1130:
1103:
1091:
1080:
1048:
1031:
1010:Baker, Brenda S.
1005:
991:Baker, Brenda S.
978:
976:
975:
970:
956:
954:
953:
948:
935:
933:
932:
927:
924:
919:
903:
901:
900:
895:
892:
887:
860:
858:
857:
852:
850:
849:
831:
829:
828:
823:
821:
820:
819:
818:
795:
793:
792:
787:
782:
781:
757:
756:
744:
743:
724:
722:
721:
716:
714:
713:
712:
711:
690:
688:
687:
682:
679:
674:
665:
664:
652:
651:
636:
634:
633:
628:
625:
620:
604:
602:
601:
596:
593:
588:
572:
570:
569:
564:
532:
530:
529:
524:
522:
521:
505:
503:
502:
497:
485:
483:
482:
477:
465:
460:
447:
442:
426:
424:
423:
418:
380:
378:
377:
372:
367:
366:
342:
341:
329:
328:
309:
307:
306:
301:
299:
277:
275:
274:
269:
257:
255:
254:
249:
237:
235:
234:
229:
224:
204:
202:
201:
196:
184:
182:
181:
176:
164:
162:
161:
156:
144:
142:
141:
136:
125:INDEPENDENT-SET(
1379:
1378:
1374:
1373:
1372:
1370:
1369:
1368:
1344:
1343:
1342:
1248:Eppstein, David
1165:
1120:
1101:
1089:
985:
964:
961:
960:
942:
939:
938:
920:
915:
909:
906:
905:
888:
883:
877:
874:
873:
867:
845:
841:
839:
836:
835:
832:
814:
810:
809:
805:
803:
800:
799:
771:
767:
752:
748:
739:
735:
730:
727:
726:
707:
703:
702:
698:
696:
693:
692:
675:
670:
660:
656:
647:
643:
641:
638:
637:
621:
616:
610:
607:
606:
589:
584:
578:
575:
574:
540:
537:
536:
517:
513:
511:
508:
507:
506:after deleting
491:
488:
487:
461:
456:
443:
438:
432:
429:
428:
388:
385:
384:
356:
352:
337:
333:
324:
320:
315:
312:
311:
284:
282:
279:
278:
263:
260:
259:
243:
240:
239:
220:
209:
206:
205:
190:
187:
186:
170:
167:
166:
150:
147:
146:
130:
127:
126:
123:
115:independent set
111:
103:1-planar graphs
77:, Fedor Fomin,
12:
11:
5:
1377:
1367:
1366:
1361:
1356:
1341:
1340:
1285:
1244:
1223:math/9907126v1
1216:(3): 275–291,
1202:
1190:(2): 166–195,
1176:
1163:
1131:
1118:
1092:
1087:
1049:
1022:(1): 153–180,
1006:
986:
984:
981:
968:
946:
923:
918:
914:
891:
886:
882:
866:
863:
848:
844:
817:
813:
808:
785:
780:
777:
774:
770:
766:
763:
760:
755:
751:
747:
742:
738:
734:
710:
706:
701:
678:
673:
669:
663:
659:
655:
650:
646:
624:
619:
615:
592:
587:
583:
562:
559:
556:
553:
550:
547:
544:
520:
516:
495:
475:
472:
469:
464:
459:
455:
451:
446:
441:
437:
416:
413:
410:
407:
404:
401:
398:
395:
392:
370:
365:
362:
359:
355:
351:
348:
345:
340:
336:
332:
327:
323:
319:
298:
295:
291:
288:
267:
247:
227:
223:
219:
216:
213:
194:
174:
154:
134:
124:
122:
119:
110:
107:
9:
6:
4:
3:
2:
1376:
1365:
1362:
1360:
1359:Planar graphs
1357:
1355:
1352:
1351:
1349:
1337:
1333:
1329:
1325:
1320:
1315:
1311:
1307:
1303:
1299:
1295:
1291:
1286:
1283:
1279:
1275:
1271:
1266:
1261:
1257:
1253:
1249:
1245:
1241:
1237:
1233:
1229:
1224:
1219:
1215:
1211:
1207:
1203:
1198:
1193:
1189:
1185:
1181:
1177:
1174:
1170:
1166:
1164:9781450306911
1160:
1155:
1150:
1146:
1142:
1138:
1132:
1129:
1125:
1121:
1119:0-7695-2468-0
1115:
1111:
1107:
1100:
1099:
1093:
1090:
1084:
1079:
1074:
1070:
1066:
1062:
1058:
1054:
1050:
1047:
1043:
1039:
1035:
1030:
1025:
1021:
1017:
1016:
1011:
1007:
1004:
1000:
996:
992:
988:
987:
980:
966:
958:
944:
921:
916:
912:
889:
884:
880:
871:
862:
846:
842:
815:
811:
806:
798:
778:
775:
772:
768:
764:
761:
758:
753:
749:
745:
740:
736:
708:
704:
699:
676:
671:
667:
661:
657:
653:
648:
644:
622:
617:
613:
590:
585:
581:
560:
557:
554:
551:
548:
545:
542:
535:
518:
514:
493:
473:
470:
467:
462:
457:
453:
449:
444:
439:
435:
414:
411:
408:
405:
402:
399:
396:
393:
390:
383:
363:
360:
357:
353:
349:
346:
343:
338:
334:
330:
325:
321:
293:
289:
265:
245:
225:
221:
217:
214:
211:
192:
172:
152:
132:
118:
116:
106:
104:
100:
96:
95:planar graphs
92:
88:
84:
80:
76:
72:
67:
65:
61:
57:
53:
49:
43:
41:
40:
35:
31:
30:planar graphs
27:
23:
19:
1301:
1298:Algorithmica
1297:
1255:
1251:
1213:
1210:Algorithmica
1209:
1206:Eppstein, D.
1187:
1183:
1154:1721.1/73855
1136:
1097:
1056:
1019:
1013:
994:
868:
833:
796:
533:
381:
112:
82:
75:Erik Demaine
68:
44:
37:
34:Brenda Baker
21:
15:
1304:(1): 1–11,
1258:(3): 1–27,
1180:Demaine, E.
1348:Categories
1319:1874/17980
1078:1874/16258
983:References
258:rooted at
79:Hajiaghayi
62:, minimum
922:ℓ
890:ℓ
847:ℓ
816:∗
812:ℓ
776:−
762:…
709:∗
705:ℓ
677:ℓ
658:∪
649:ℓ
623:ℓ
591:ℓ
561:…
519:ℓ
471:…
463:ℓ
445:ℓ
412:−
403:…
391:ℓ
361:−
347:…
226:ϵ
173:ϵ
121:Algorithm
117:problem.
42:in 1994.
1292:(2007),
1173:16516718
1128:13238254
573:compute
1336:8174422
1328:2344391
1282:2303110
1274:1750082
1240:3172160
1046:9706753
1038:1369197
1334:
1326:
1280:
1272:
1238:
1171:
1161:
1126:
1116:
1085:
1044:
1036:
797:return
1332:S2CID
1278:S2CID
1236:S2CID
1218:arXiv
1169:S2CID
1124:S2CID
1102:(PDF)
1042:S2CID
936:is a
1159:ISBN
1114:ISBN
1083:ISBN
691:let
73:of
69:The
1314:hdl
1306:doi
1260:doi
1228:doi
1192:doi
1149:hdl
1141:doi
1106:doi
1073:hdl
1065:doi
1024:doi
999:doi
534:for
486:of
382:for
290:mod
16:In
1350::
1330:,
1324:MR
1322:,
1312:,
1302:49
1300:,
1296:,
1276:,
1270:MR
1268:,
1254:,
1234:,
1226:,
1214:27
1212:,
1188:69
1186:,
1167:,
1157:,
1147:,
1122:,
1112:,
1081:,
1071:,
1059:,
1040:,
1034:MR
1032:,
1020:41
1018:,
310::
165:,
145:,
105:.
58:,
54:,
50:,
20:,
1339:.
1316::
1308::
1262::
1256:3
1243:.
1230::
1220::
1201:.
1194::
1151::
1143::
1108::
1075::
1067::
1026::
1001::
967:k
945:k
917:i
913:G
885:i
881:G
843:S
807:S
784:}
779:1
773:k
769:S
765:,
759:,
754:1
750:S
746:,
741:0
737:S
733:{
700:S
672:i
668:S
662:i
654:=
645:S
618:i
614:G
586:i
582:S
558:,
555:2
552:,
549:1
546:=
543:i
515:V
494:G
474:,
468:,
458:2
454:G
450:,
440:1
436:G
415:1
409:k
406:,
400:,
397:0
394:=
369:}
364:1
358:k
354:V
350:,
344:,
339:1
335:V
331:,
326:0
322:V
318:{
297:)
294:k
287:(
266:r
246:G
222:/
218:1
215:=
212:k
193:r
153:w
133:G
89:,
85:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
