Some Results On Reconfiguration Graphs Of Independent Sets
Some Results onReconfiguration Graphs of Independent SetsMay 13, 2021Duc A. HoangKyushu Institute of Technology, Japanhoanganhduc@ces.kyutech.ac.jpResearch Seminar at Kyutech Algorithms Group
OutlineSome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangIntroductionIntroductionCombinatorial ReconfigurationIndependent SetsReconfiguration Graphs of Independent SetsCombinatorialReconfigurationIndependent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and CyclesSome Questions and ResultsObservationsTypical QuestionsTrees and CyclesBibliography15
IntroductionCombinatorial ReconfigurationSome Results onReconfigurationGraphs of IndependentSets. is the study of reconfiguration graphs.Duc A. Hoangadjacency relation[reconfiguration pendent SetsReconfiguration Graphs ofIndependent SetsconfigurationsSome Questions andResultsreconfiguration graphObservationsTypical QuestionsTypical PropertiesTrees and CyclesBibliographyadjacency is polynomial testable.reconfiguration graph is huge.Reconfiguration v.s. Solution Spaceconfigurations feasible solutions of a problem.reconfiguration rule small change that preserves the“feasibility” of a solution.15
IntroductionCombinatorial ReconfigurationSome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangExamples of Reconfiguration Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and CyclesBibliographyFigure: Games and Puzzles.[Anna Lubiw, CoRe2019]Figure: Frequency Re-Assignmentand Vertex-Recoloring.15
IntroductionIndependent SetsSome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangAn independent set of a graph G (V, E) is a vertex-subsetI V such that for any pair u, v I, no edge connects u and dent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and CyclesBibliographyFigure: Example of an independent set whose members are depictedwith black tokens.15
IntroductionReconfiguration Graphs of Independent SetsSome Results onReconfigurationGraphs of IndependentSetsLet G (V, E) be a graph on n vertices.Under Token Sliding: TSk (G)Duc A. HoangEach node is an independent set of size k.Two nodes I, J are adjacent if there exist x, y V suchthat I \ J {x}, J \ I {y}, and xy endent Sets5Reconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and CyclesBibliographyFigure: TS1 (P3 ).15
IntroductionReconfiguration Graphs of Independent SetsSome Results onReconfigurationGraphs of IndependentSetsLet G (V, E) be a graph on n vertices.Under Token Jumping: TJk (G)Duc A. HoangEach node is an independent set of size k.Two nodes I, J are adjacent if there exist x, y V suchthat I \ J {x}, J \ I {y}, and xy endent Sets5Reconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and CyclesBibliographyFigure: TJ1 (P3 ).15
IntroductionReconfiguration Graphs of Independent SetsSome Results onReconfigurationGraphs of IndependentSetsLet G (V, E) be a graph on n vertices.Under Token Addition/Removal: TARk (G)Duc A. HoangEach node is an independent set of size at least k.Two nodes I, J are adjacent if there exists x V suchthat I J (I \ J) (J \ I) ndent Sets5Reconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and CyclesBibliographyFigure: TAR1 (P3 ).15
Some Questions and ResultsObservationsSome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangLet G (V, E) be a graph on n vertices. Recall that twographs G, H are isomorphic, denoted by G ' H, if there is abijection f : V (G) V (H) such that for any pair u, v V (G),uv E(G) if and only if f (u)f (v) E(H).For two independent sets I, J of size k, there is a pathbetween them in TJk (G) if and only if there is a pathbetween them in TARk 1 (G) (see [Kamiński et al. ependent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResults6ObservationsTypical QuestionsTrees and CyclesBibliography15
Some Questions and ResultsObservationsSome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangLet G (V, E) be a graph on n vertices. Recall that twographs G, H are isomorphic, denoted by G ' H, if there is abijection f : V (G) V (H) such that for any pair u, v V (G),uv E(G) if and only if f (u)f (v) E(H).For two independent sets I, J of size k, there is a pathbetween them in TJk (G) if and only if there is a pathbetween them in TARk 1 (G) (see [Kamiński et al. ependent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResults6ObservationsTypical QuestionsTrees and CyclesBibliographyBy definition, TSk (G) is a spanning subgraph of TJk (G).15
Some Questions and ResultsObservationsSome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangLet G (V, E) be a graph on n vertices. Recall that twographs G, H are isomorphic, denoted by G ' H, if there is abijection f : V (G) V (H) such that for any pair u, v V (G),uv E(G) if and only if f (u)f (v) E(H).For two independent sets I, J of size k, there is a pathbetween them in TJk (G) if and only if there is a pathbetween them in TARk 1 (G) (see [Kamiński et al. ependent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResults6ObservationsTypical QuestionsTrees and CyclesBibliographyBy definition, TSk (G) is a spanning subgraph of TJk (G).If k α(G)—the maximum size of an independent set ofG—then TSk (G) ' TJk (G). If k 1, then TSk (G) ' G andTJk (G) ' Kn .15
Some Questions and ResultsTypical QuestionsSome Results onReconfigurationGraphs of IndependentSetsLet G (V, E) be a graph on n vertices. Suppose thatR {TS, TJ, TAR}. Typically, one may askDuc A. HoangIntroduction1. Given two nodes I, J of Rk (G), is there a (shortest) pathbetween them? If yes, can we find it t SetsReconfiguration Graphs ofIndependent Sets2. Is Rk (G) connected?Some Questions andResults3. Does Rk (G) belong to some graph class G?4. Does there exist a graph G that is isomorphic to Rk (G),or, at least, in the same graph class as Rk (G)?Observations7Typical QuestionsTrees and CyclesBibliography5. and so on.Note: Alikhani and Fatehi [Alikhani and Fatehi 2017] initiatedthe study of Question 3 for TARk (G). In this talk, we will focuson finding some structural properties of TSk (G) when G iseither a tree or a cycle.15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsLemmaLet Tn and Cn be respectively a tree and a cycle on n vertices.Then,Duc A. HoangIntroduction(a) TSk (Tn ) is bipartite.CombinatorialReconfiguration(b) TSk (Cn ) is bipartite when n is even; otherwise, it is not.Moreover, when n is odd and k α(Cn ) bn/2c, we haveTSk (Cn ) ' Cn .Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical Questions8Trees and CyclesBibliography15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsLemmaLet Tn and Cn be respectively a tree and a cycle on n vertices.Then,Duc A. HoangIntroduction(a) TSk (Tn ) is bipartite.CombinatorialReconfiguration(b) TSk (Cn ) is bipartite when n is even; otherwise, it is not.Moreover, when n is odd and k α(Cn ) bn/2c, we haveTSk (Cn ) ' Cn .Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsHint.Typical Questions8Let I {v1 , . . . , vk } V (TSk (G)); and token ti be on vi .Suppose that there is a cycle C in TSk (G) containing I.Trees and CyclesBibliographyObservationTo form C, tokens must be moved based on some permutationπ of v1 , . . . , vk , i.e., token ti on vi will finally move to π(vi ).15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsHint (cont.)(a) In a tree Tn , the only way to slide ti from vi to π(vi ) isthrough the unique vi π(vi )-path. There are two types oftoken-slides:Duc A. HoangIntroductionCombinatorialReconfiguration(1) blue token-slides: along the vi π(vi )-path;(2) red token-slides: outside the vi π(vi )-path.Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical Questions9Trees and CyclesBibliographyFigure: Possible types of token-slides when moving ti .PkTo form C, we need 2 i 1 distTn (vi , π(vi )) blue someeven number of red token-slides.15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsHint (cont.)(b) In a cycle Cn , the permutation π defined by π(vi ) vi 1for i {1, . . . , k 1} and π(vk ) v1 can be usedrepeatedly to generate any C (if it exists).Duc A. endent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical Questions10Trees and CyclesBibliographyFigure: The permutation π helps generating any cycle C inTSk (Cn ) containing I. The arrows indicate next targets.15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsA graph is Eulerian if it is connected and has a closed walkcontaining all edges. Let Cn w1 . . . wn w1 .Duc A. HoangLemmaIntroductionTSk (Cn ) is ent SetsReconfiguration Graphs ofIndependent SetsNote that a graph is Eulerian if and only if every vertex haseven degree. Let I TSk (Cn ). The cycle Cn containstoken-paths and empty-paths.token-paths: wi wi 1 . . . wj , where wi , wi 2 , wi 4 , . . . , wjcontain tokens.Some Questions andResultsObservationsTypical Questions11Trees and CyclesBibliographyempty-paths: no tokens length 2.15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsQuestionCan we findDuc A. Hoanga graph G, andIntroductionCombinatorialReconfigurationa property P,Independent Setssuch that G and TSk (G) both satisfy P?Reconfiguration Graphs ofIndependent SetsSome Questions andResultsG is either Tn or Cn , and P is “being bipartite”.G is Cn , and P is “being Eulerian”.ObservationsTypical Questions12Trees and CyclesBibliographyAnother example?15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsQuestionCan we findDuc A. Hoanga graph G, andIntroductionCombinatorialReconfigurationa property P,Independent Setssuch that G and TSk (G) both satisfy P?Reconfiguration Graphs ofIndependent SetsSome Questions andResultsG is either Tn or Cn , and P is “being bipartite”.G is Cn , and P is “being Eulerian”.ObservationsTypical Questions12Trees and CyclesBibliographyAnother example?QuestionThe girth of a graph is the size of its smallest cycle. If a graphhas no cycle, its girth is . What about girth(TSk (Tn ))?From the above Lemma, girth(TSk (Cn )) is either n or .15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsLemmaLet Pn and Cn be respectively a path and a cycle on n vertices.Then, for n large enough, and some kDuc A. HoangIntroduction(a) TSk (Pn ) is not planar. Thus, so is TJk (Pn ).CombinatorialReconfiguration(b) TSk (Cn ) is not planar. Thus, so is TJk (Cn ).Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical Questions13Trees and CyclesBibliography15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsLemmaLet Pn and Cn be respectively a path and a cycle on n vertices.Then, for n large enough, and some kDuc A. HoangIntroduction(a) TSk (Pn ) is not planar. Thus, so is TJk (Pn ).CombinatorialReconfiguration(b) TSk (Cn ) is not planar. Thus, so is TJk (Cn ).Independent SetsReconfiguration Graphs ofIndependent SetsHint (based on comments from David Avis-sensei,KyotoU).Consider the graph Gn whose components are TSk (Pn ), fork {0, 1, 2, . . . , α(G)}.P(a) Let f (n) V (Gn ) and g(n) I V (Gn ) degGn (I). WehaveSome Questions andResultsObservationsTypical Questions13f (n) f (n 1) f (n 2) for n 2; f (0) 1; f (1) 2.g(n) g(n 1) g(n 2) 2f (n 3) for n 3; g(0) 0;g(1) 0; g(2) 2.If Gn is planar, we must have g(n) 2(3f (n) 6) for everyn. This does not hold when n 19. [Please verify!]Trees and CyclesBibliography15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsLemmaLet Pn and Cn be respectively a path and a cycle on n vertices.Then, for n large enough, and some kDuc A. HoangIntroduction(a) TSk (Pn ) is not planar. Thus, so is TJk (Pn ).CombinatorialReconfiguration(b) TSk (Cn ) is not planar. Thus, so is TJk (Cn ).Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsHint.Consider the graph Gn whose components are TSk (Cn ), fork {0, 1, 2, . . . , α(G)}.ObservationsTypical Questions14Trees and CyclesBibliography(b) Take a vertex v of Cn . For each k, the subgraph ofTSk (Cn ) induced by nodes (independent sets) that do notcontain v is indeed isomorphic to TSk (Pn 1 ). Note thatevery subgraph of a planar graph must be also planar.Note: Consequently, there is a maximal outerplanar graph Gsuch that TSk (G) and TJk (G) are both non-planar for some k.15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsQuestionFor which value of k, TSk (Pn ) is planar , for any n?Duc A. ally, k 1 or k bn/2c. Any non-trivial bound?Independent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical Questions15Trees and CyclesBibliography15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsQuestionFor which value of k, TSk (Pn ) is planar , for any n?Duc A. ally, k 1 or k bn/2c. Any non-trivial bound?Independent SetsReconfiguration Graphs ofIndependent SetsQuestionSome Questions andResultsCan we find a graph G such that TSk (G) is planar ?ObservationsTypical QuestionsTrivially, one can take a star graph K1,n (i.e., a treeformed by joining n leaves to a center vertex.).15Trees and CyclesBibliography15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsQuestionFor which value of k, TSk (Pn ) is planar , for any n?Duc A. ally, k 1 or k bn/2c. Any non-trivial bound?Independent SetsReconfiguration Graphs ofIndependent SetsQuestionSome Questions andResultsCan we find a graph G such that TSk (G) is planar ?ObservationsTypical QuestionsTrivially, one can take a star graph K1,n (i.e., a treeformed by joining n leaves to a center vertex.).My guess: G can be a double-star graph (i.e., a treeformed by joining the centers of two disjoint stars).Moreover, when G is double-star, TSk (G) is a tree.15Trees and CyclesBibliography15
Some Questions and ResultsTrees and CyclesSome Results onReconfigurationGraphs of IndependentSetsQuestionFor which value of k, TSk (Pn ) is planar , for any n?Duc A. ally, k 1 or k bn/2c. Any non-trivial bound?Independent SetsReconfiguration Graphs ofIndependent SetsQuestionSome Questions andResultsCan we find a graph G such that TSk (G) is planar ?ObservationsTypical QuestionsTrivially, one can take a star graph K1,n (i.e., a treeformed by joining n leaves to a center vertex.).My guess: G can be a double-star graph (i.e., a treeformed by joining the centers of two disjoint stars).Moreover, when G is double-star, TSk (G) is a tree.More general guess: We knew that TSk (G) isnon-planar for some k when G is a “long” path. Thus, tomake it planar, we might take G as a tree with some smalldiameter d?15Trees and CyclesBibliography15
BibliographySome Results onReconfigurationGraphs of IndependentSetsDuc A. HoangIntroductionAlikhani, Saeid and Davood Fatehi (2017). “Thek-Independent Graph of a Graph”. In: Advances andApplications in Discrete Mathematics 18.1, pp. 45–56.DOI : 10.17654/dm018010045. arXiv: 1510.05360.Kamiński, Marcin, Paul Medvedev, and Martin Milanič(2012). “Complexity of Independent Set ReconfigurabilityProblems”. In: Theoretical Computer Science 439,pp. 9–15. DOI: tionIndependent SetsReconfiguration Graphs ofIndependent SetsSome Questions andResultsObservationsTypical QuestionsTrees and Cycles1515Bibliography
May 13, 2021 · Duc A. Hoang Introduction Combinatorial Reconfiguration 4 Independent Sets Reconfiguration Graphs of Independent Sets Some Questions and Results Observations Typical Questions Trees and Cycles Bibliography Introduction Independent Sets An independent set of a graph G (V,E) is a v
2 Vivado Partial Reconfiguration - Documentation UG909: Vivado Design Suite User Guide - Partial Reconfiguration. UG947: Vivado Design Suite Tutorial - Partial Reconfiguration. You can follow this for the Xilinx-provided ug947-vivado-partial-reconfiguration-tutorial.zip file (this is a Verilog design for
IBI GROUP DESIGN STUDY REPORT DIXIE ROAD LANE RECONFIGURATION Prepared for Region of Peel Document Control Page September 2, 2016 CLIENT: Region of Peel PROJECT NAME: Dixie Road Lane Reconfiguration Preliminary and Detail Design REPORT TITLE: Dixie Road Lane Reconfiguration IBI REFERENCE: 38948 VERSION: 4 DIGITAL MASTER: Hamilton J:\38948_DixieRd\10.0 Reports
Math 6 NOTES Name _ Types of Graphs: Different Ways to Represent Data Line Graphs Line graphs are used to display continuous data. Line graphs can be useful in predicting future events when they show trends over time. Bar Graphs Bar graphs are used to display categories of data.
difierent characterizations of pushdown graphs also show the limited expres-siveness of this formalism for the deflnition of inflnite graphs. Preflx Recognizable Graphs. The equivalence of pushdown graphs to the graphs generated by preflx rewriting systems on words leads to a natural extension of pushdown graphs.
proposes a distribution system reconfiguration method based on linear programming power distribution system reconfiguration. The improved simplex method is used to find the optimal combination of switches. Das [11] proposed a multi objective method which combines the optimization algorithm with heuristic rules and fuzzy logic. The
Dynamic cache reconfiguration is a promising approach for reducing energy consumption as well as for improving overall system performance. It is a major challenge to introduce cache reconfiguration into real-time multitasking systems, since dynamic analysis may adversely affect tasks with timing constraints.
Dynamic Cache Reconfiguration for Soft Real-Time Systems 1:3 2. RELATED WORK Nacul et al. [Nacul and Givargis 2004] proposed an initial work on combining dynamic voltage scheduling and cache reconfiguration on workloads with time constraints. However, their work is applicable in a very restricted scenario where systems does not support task .
Excellence Model and its suitability for measuring the levels of business excellence is being demonstrated. The second part is dedicated to the exploration and presentation of alternative ways for attaining the highest possible levels of excellence, while, in the third part a comprehensive comparison among them is being conducted. Finally, in the fourth part, the basic findings are summarized .
