/* ===== Input file for the Subgraph Isomorphism project ===== Authors: Daniel Marx and Michal Pilipczuk Format: The file consist of 3 sections, each beginning with a keyword defining this section. #PARAMETERS - a list of parameters follows #RELATIONS - a list of relations follows Simple relation: (par) -> (par) Implicit relation: (par) (par) ... -> (par) Meaning: Assuming all the prerequisites on the left side, right side follows. #RESULTS - a list of results follows, in format positive (par) (par) (par) ... negative (par) (par) (par) ... #END - obligatory at the end of file Use of standard C comments is allowed, as well as keywords xxref and xxname followed by one unparsed string (used for automatic generation of tex files). ============================================================ */ #PARAMETERS degH2 degH3 degH_par degH_exp fvsH_par fvsH_exp pwH_par pwH_exp twH1 twH_par twH_exp cwH_exp cwH_par VH_par planarH genusH_par genusH_exp minorH_par minorH_exp topH_par topH_exp ccH_par ccH_exp connH degG2 degG3 degG_par degG_exp fvsG_par fvsG_exp pwG_par pwG_exp twG1 twG_par twG_exp cwG_exp cwG_par planarG genusG_par genusG_exp minorG_par minorG_exp topG_par topG_exp ccG_par ccG_exp connG #RELATIONS /* Standard relations */ /* (b) */ degH_exp -> degH_par pwH_exp -> twH_exp pwH_exp -> pwH_par fvsH_exp -> fvsH_par twH_exp -> twH_par cwH_exp -> cwH_par genusH_exp -> genusH_par minorH_exp -> minorH_par topH_exp -> topH_par ccH_exp -> ccH_par degG_exp -> degG_par pwG_exp -> pwG_par fvsG_exp -> fvsG_par twG_exp -> twG_par cwG_exp -> cwG_par genusG_exp -> genusG_par minorG_exp -> minorG_par topG_exp -> topG_par ccG_exp -> ccG_par /* (d) */ degH3 -> degH_exp planarH -> genusH_exp connH -> ccH_exp degG3 -> degG_exp planarG -> genusG_exp connG -> ccG_exp /* (e)(i) */ degG_par -> degH_par degG_exp -> degH_exp fvsG_par -> fvsH_par pwG_par -> pwH_par twG_par -> twH_par fvsG_exp -> fvsH_exp pwG_exp -> pwH_exp twG_exp -> twH_exp genusG_par -> genusH_par genusG_exp -> genusH_exp minorG_par -> minorH_par minorG_exp -> minorH_exp /* (e)(ii) */ twG1 -> twH1 degG2 -> degH2 degG3 -> degH3 planarG -> planarH /* (e)(iii) */ connH -> connG /* (e)(iv) */ degH2 -> pwH_exp degH2 -> twH_exp degH2 -> planarH degH2 -> degH3 degG2 -> pwG_exp degG2 -> twG_exp degG2 -> planarG degG2 -> degG3 /* (e)(v) */ twH1 -> fvsH_exp twH1 -> planarH twG1 -> fvsG_exp twG1 -> planarG /* (e)(vi) */ VH_par -> genusH_par VH_par -> ccH_par VH_par -> degH_par VH_par -> cwH_par VH_par -> pwH_par VH_par -> fvsH_par pwH_exp -> twH_exp pwH_par -> twH_par fvsH_exp -> twH_exp fvsH_par -> twH_par twH_exp -> cwH_exp twH_par -> cwH_par twH_exp -> minorH_exp twH_par -> minorH_par genusH_exp -> minorH_exp genusH_par -> minorH_par minorH_exp -> topH_exp minorH_par -> topH_par degH_exp -> topH_exp degH_par -> topH_par topH_exp cwH_exp -> twH_exp topH_par cwH_par -> twH_par pwG_exp -> twG_exp pwG_par -> twG_par fvsG_exp -> twG_exp fvsG_par -> twG_par twG_exp -> cwG_exp twG_par -> cwG_par twG_par -> minorG_par twG_exp -> minorG_exp genusG_exp -> minorG_exp genusG_par -> minorG_par minorG_exp -> topG_exp minorG_par -> topG_par degG_exp -> topG_exp degG_par -> topG_par topG_exp cwG_exp -> twG_exp topG_par cwG_par -> twG_par #RESULTS /* ============================================ Section 3 ============================================ */ /* Theorem P.1 FO Model Checking for bounded-cliquewidth graphs */ xxname P.1 xxref thm:FOcw positive VH_par cwG_par /* Theorem P.2 FO Model Checking for topological-minor-free graphs */ xxname P.2 xxref thm:FOtopmin positive VH_par topG_par /* Theorem P.3 Color coding */ xxname P.3 xxref thm:colour-coding positive twH_exp VH_par /* Theorem P.4 Slightly stronger version of the Matousek and Thomas algorithm: we may have the number of connected components of H in the multiplier. A simple reduction from the original algorithm of Matousek and Thomas */ xxname P.4 xxref thm:strong-MT positive ccH_par degH_par twG_exp /* Theorem P.5 Simple packing of paths and cycles into paths and cycles */ xxname P.5 xxref thm:vcG positive degG2 ccG_exp /* Theorem P.6 Long path&cycles in bounded tw, classical tw DP. */ xxname P.6 xxref thm:dpCyclesParTw positive degH2 twG_par ccH_exp /* Theorem P.7 Long path&cycles in constant cw, classical cw DP. */ xxname P.7 xxref thm:cwdp positive degH2 cwG_exp ccH_exp /* Theorem P.8 Packing forest into a forest. Use the randomized algorithm of Mulmuley et al. to perform the matching step in the DP. */ xxname P.8 xxref thm:treesintotrees positive twG1 ccH_par /* ============================================ Section 4 ============================================ */ /* Theorem P.9 Packing a bounded number of paths and cycles into a constant genus graph with bounded degree and feedback vertex set. Just apply the structural result (Lemma 4.1) and branch. */ xxname P.9 xxref th:cyclefvs positive degG_par fvsG_par ccH_par degH2 /* Theorem P.10 The large CSP algorithm exploiting bounded degree, feedback vertex set, and constant genus. */ xxname P.10 xxref th:bigplanar positive degG_par fvsG_par genusG_exp ccH_exp /* Theorem P.11 Lifting the algorithm of Theorem P.10 to minor-free graphs */ xxname P.11 xxref th:bigplanarminor positive degH_exp degG_par fvsG_par minorG_exp ccH_exp /* ============================================ Section 5 ============================================ */ /* Theorem N.1 Bin packing: paths into paths */ xxname N.1 xxref thm:bin-packing negative twG1 degG2 ccG_par /* Theorem N.2 Bin packing: universal vertex in G, and a preimage in H connected only to one vertex of each path */ xxname N.2 xxref thm:bin-packing-univ negative connH twH1 pwG_exp fvsG_exp planarG /* Theorem N.3 Bin packing: paths into paths connected by a long path */ xxname N.3 xxref thm:bin-packing-path negative degH2 degG3 twG1 pwG_exp connG /* Theorem N.4 Hamiltonian path in cubic planar graphs, Garey et al. [SICOMP 1976] */ xxname N.4 xxref thm:planar-cubic negative twH1 degH2 connH degG3 planarG /* Theorem N.5 Clique subgraph */ xxname N.5 xxref thm:clique negative cwH_exp connH VH_par /* Theorem N.6 Hamiltonian path in bounded cw, Fomin et al. [SODA 2009] */ xxname N.6 xxref thm:hampath-cliquewidth negative degH2 connH cwG_par twH1 /* ============================================ Section 6 ============================================ */ /* Theorem N.7 Packing a bounded number of trees of constant pathwidth into a planar subcubic graph of bounded pw and fvs. Reduction from Grid Tiling using bounded pw 1-in-n gadgets packed into node grid, without connection in H. */ xxname N.7 xxref thm:grid-manycomp negative pwH_exp twH1 ccH_par degG3 pwG_par fvsG_par connG planarG /* Theorem N.8 Packing a tree of constant pathwidth into a bounded-genus graph of bounded pw, fvs and with excluded K_7 minor. Reduction from Grid Tiling using bounded pw 1-in-n gadgets packed into node grid, with one-vertex connection in H. */ xxname N.8 xxref thm:many-comp-minor negative pwH_exp twH1 connH degG_par pwG_par fvsG_par genusG_par minorG_exp /* Theorem N.9 Packing a tree of constant pathwidth into a subcubic bounded-genus graph of bounded pw and fvs. Reduction from Grid Tiling using bounded pw 1-in-n gadgets packed into node grid, with path-like connection in H. */ xxname N.9 xxref thm:many-comp-genus negative pwH_exp twH1 connH degG3 pwG_par fvsG_par genusG_par /* Theorem N.10 Version of Theorem N.9 with biclique gadgets introduced to ensure constant cliquewidth. */ xxname N.10 xxref thm:grid-manycomp-conn-many-biclique negative pwH_exp twH1 connH degH3 degG_par pwG_par fvsG_par genusG_par cwG_exp /* Theorem N.11 Packing a tree of constant pathwidth into a planar graph of bounded pw and fvs. Reduction from Grid Tiling using moustache gadgets in order to preserve connectivity of H. Version that has unbounded degree, but bounded feedback vertex set number. */ xxname N.11 xxref thm:grid-connfvs negative pwH_exp connH twH1 degH3 pwG_par fvsG_par planarG /* Theorem N.12 Packing a tree of constant pathwidth into a subcubic planar graph of bounded pw. Reduction from Grid Tiling using moustache gadgets in order to preserve connectivity of H. Version that has unbounded feedback vertex set number, but bounded degree. */ xxname N.12 xxref thm:grid-conndegree negative pwH_exp connH twH1 degG3 pwG_par planarG /* Theorem N.13 Packing a small planar graph into a large graph of bounded pw and fvs. Reduction from Grid Tiling, add small gadgets using Lemma 2.6 to enforce that the grid nodes are mapped appropriately. */ xxname N.13 xxref thm:multicolored-grid negative degH3 connH planarH VH_par /* Theorem N.14 Packing bounded number of long paths into a planar of bounded pw and fvs. Reduction from Exact Planar Arc Supply, version that uses gadgets for arcs that ensure bounded feedback vertex set number but unbounded degree. */ xxname N.14 xxref thm:expas-fvs negative twH1 degH2 ccH_par pwG_par fvsG_par planarG connG /* Theorem N.15 Packing bounded number of long paths into a planar of bounded pw and degree. Reduction from Exact Planar Arc Supply, version that uses gadgets for arcs that ensure bounded degree but unbounded feedback vertex set number. */ xxname N.15 xxref thm:expas-degree negative twH1 degH2 ccH_par degG3 pwG_par planarG connG /* Theorem N.16 Version of Theorem N.14 with bicliques to ensure constant cliquewidth. */ xxname N.16 xxref thm:expas-fvs-biclique negative twH1 degH2 ccH_par pwG_par fvsG_par cwG_exp genusG_par connG /* Theorem N.17 Version of Theorem N.15 with bicliques to ensure constant cliquewidth. */ xxname N.17 xxref thm:expas-degree-biclique negative twH1 degH2 ccH_par degG_par pwG_par cwG_exp genusG_par connG #END