Preface
Organization
Contents
Minimal Roman Dominating Functions: Extensions and Enumeration
1 Introduction
2 Definitions
3 Properties of Minimal Roman Dominating Functions
4 A Polynomial-Time Algorithm for ExtRD
5 Enumerating Minimal RDF for General Graphs
6 A Refined Enumeration Algorithm
6.1 A Bird's Eye View on the Algorithm
6.2 How to Achieve Polynomial Delay and Polynomial Space
6.3 Details on Reductions and Branchings
6.4 A Measure and Conquer Approach
7 An Alternative Notion of Minimal RDF
8 Conclusions
References
Disjoint Compatibility via Graph Classes
1 Introduction
2 Preliminaries
3 Disjoint Compatibility via Spanning Trees
3.1 A Lower Bound for the Diameter of DCGS(T)
4 Disjoint Caterpillar-Compatible Matchings
5 Disjoint Path-Compatible Matchings
6 Conclusion and Discussion
References
Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed-Parameter Tractable (Extended Abstract)
1 Introduction
2 Preliminaries
3 Chordal Graphs
3.1 Stable Colorings in Chordal Graphs
3.2 Estimates Depending on the Leafage
4 Critical Set of a Chordal Graph
5 The Hypergraph Associated with the Complement of the Critical Set
6 Order-k Hypergraph Isomorphism: Bounded Color Classes
7 Main Algorithm and the Proof of Theorem 2
8 Concluding Remarks
References
Twin-Width and Transductions of Proper k-Mixed-Thin Graphs
1 Introduction
1.1 Outline of the Paper
2 Preliminaries and Formal Definitions
2.1 Intersection Graphs
2.2 Twin-Width
2.3 FO Logic and Transductions
3 Generalizing Proper k-Thin Graphs
3.1 Comparing (Proper) k-Mixed-Thin to Other Classes
4 Proper k-Mixed-Thin Graphs Have Bounded Twin-Width
5 Transductions Between Inversion-Free Proper k-Mixed-Thin Graphs and Posets
6 Conclusions
References
Token Sliding on Graphs of Girth Five
1 Introduction
2 Preliminaries
3 The Algorithm
3.1 Safe, Bounded, and Bad Components
3.2 Bounding the Size of L2
3.3 Bounding the Size of L3
References
Recognition of Linear and Star Variants of Leaf Powers is in P
1 Introduction
2 Preliminaries
3 Linear Leaf Powers
4 Star NeS Model
References
Problems Hard for Treewidth but Easy for Stable Gonality
1 Introduction
2 Preliminaries
2.1 Conventions and Notations
2.2 Stable Gonality and Treebreadth
3 Related Problems and Reductions
4 Algorithms for ORO and CDS for Graphs with Bounded Treebreadth
4.1 Outdegree Restricted Orientations
4.2 Capacitated Dominating Set
5 Conclusion
References
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
1 Introduction
2 Preliminaries
3 Edge-Cut Width
4 Computing Edge-Cut Width
5 Algorithmic Applications of Edge-Cut Width
6 Conclusion
References
An Algorithmic Framework for Locally Constrained Homomorphisms
1 Introduction
2 Preliminaries
3 Our Algorithmic Framework
4 Applications of Our Algorithmic Framework
5 Conclusions
References
s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
1 Introduction
2 Our Contributions
3 Polynomial Time Algorithm for CVD on Well-Partitioned Chordal Graphs
3.1 Finding Minimum X-CVD Sets
3.2 Finding Minimum (X,Y)-CVD Set of Well-partitioned Chordal Graphs
3.3 Main Algorithm
4 Hardness for Well-Partitioned Chordal Graphs
5 O(n(n+m))-Time Algorithm for s-CVD on Interval Graphs
5.1 The Algorithm
5.2 Time Complexity
References
Polychromatic Colorings of Unions of Geometric Hypergraphs
1 Introduction
1.1 Related Work
1.2 Our Results
2 Polychromatic Colorings for Two Range Families
3 Families of Unbounded Rectangles
3.1 The Case with No Polychromatic Coloring: Bottomless Rectangles and Horizontal Strips
3.2 The Cases with Polychromatic Colorings
4 Concluding Remarks
References
Kernelization for Feedback Vertex Set via Elimination Distance to a Forest
1 Introduction
2 Preliminaries
2.1 Elimination Distance
3 Kernelization Upper Bounds
4 Kernelization Lower Bounds
5 Conclusion and Discussion
References
Finding k-Secluded Trees Faster
1 Introduction
2 Framework for Enumerating Secluded Trees
3 Enumerate Large Secluded Supertrees
3.1 Subroutines for the Algorithm
3.2 The Algorithm
3.3 Proof of Correctness
3.4 Runtime Analysis
3.5 Finding, Enumerating, and Counting Large Secluded Trees
4 Conclusion
References
On the Minimum Cycle Cover Problem on Graphs with Bounded Co-degeneracy
1 Introduction
2 On the Stability of Having a Bounded Cycle Cover
3 Polynomial Kernelization
4 An Exact Single-Exponential Time Algorithm
References
On the Lossy Kernelization for Connected Treedepth Deletion Set
1 Introduction
2 Preliminaries
3 Approximate Kernel for Connected -Treedepth Deletion
3.1 Decomposition of the Graph G
3.2 Processing Connected Components of G - (X Z) with Large Neighborhoods
3.3 Understanding the Structure of a Good Solution
3.4 Identifying Further Irrelevant Vertices
4 Conclusions
References
Generalized k-Center: Distinguishing Doubling and Highway Dimension
1 Introduction
1.1 Used Techniques
2 Inapproximability in Low Highway Dimension Graphs
3 EPAS on Graphs of Bounded Doubling Dimension
4 Open Problems
References
Extending Partial Representations of Circular-Arc Graphs
1 Introduction
2 Preliminaries
3 Complexity
4 (Normal) Proper Helly Circular-Arc Graphs
5 (Normal) Helly Circular-Arc Graphs
6 Conclusions and Open Problems
References
Bounding Threshold Dimension: Realizing Graphic Boolean Functions as the AND of Majority Gates
1 Introduction
1.1 Our Results
1.2 Preliminaries
2 Threshold Dimension and Treewidth
3 Threshold Dimension and Maximum Degree
4 Threshold Dimension and Degeneracy
4.1 Random Graphs
4.2 Graphs of High Girth
5 Threshold Dimension and Minimum Vertex Cover
References
Parameterized Complexity of Weighted Multicut in Trees
1 Introduction
2 Basic Notation
3 wMC-Tree Parameterized by the Solution Size
4 uwMC-Tree Parameterized by the Number of Leaves
5 Future Directions
References
The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs
1 Introduction
2 Triconnected 4-Regular Planar Graphs
3 Maximal Outerpaths
4 Further Results and Open Problems
References
Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs
1 Introduction
2 Preliminaries
3 Twin-Width of Graphs of Bounded Treewidth
4 Twin-Width of Planar Graphs
5 Bipartite Graph
6 Conclusion
References
On Anti-stochastic Properties of Unlabeled Graphs
1 Introduction
2 Preliminaries
3 Proof of Theorem 1
4 Proof of Theorem 2
5 Conclusion and Further Questions
References
Computing List Homomorphisms in Geometric Intersection Graphs
1 Introduction
2 Preliminaries
3 Algorithm for Intersection Graphs of Fat Objects
4 Lower Bound for Intersection Graphs of Disks
5 Conclusion and Open Problems
References
On Fully Diverse Sets of Geometric Objects and Graphs
1 Introduction
2 Fair Bit Strings
3 Geometric Diversity
4 Embedding Diversity
5 Abstract Graphs
6 Conclusions and Open Problems
References
Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings
1 Introduction
2 Preliminaries
3 Hardness of the Extension Problem
4 Enumeration of Maximal Matchings
4.1 Large Maximal Matching Enumeration
4.2 k-Best Maximal Matching Enumeration
References
The Complexity of Contracting Bipartite Graphs into Small Cycles
1 Introduction
2 C5-Contractibility on Bipartite Graphs
2.1 Construction of H and G
2.2 Equivalence of H and G
2.3 Properties of a C5-Witness Structure of H
2.4 Equivalence of H and
3 C4-Contractiblity on Biparitite Graphs
3.1 Construction of G
3.2 Properties of a Nice C4-Witness Structure of G
3.3 Equivalence of G and
4 Conclusion and Future Directions
References
Algorithmic Aspects of Small Quasi-Kernels
1 Introduction
2 Disjoint Quasi-Kernels
3 Acyclic Digraphs
4 Orientations of Split Graphs
4.1 Computational Hardness
4.2 Complete Split Graphs
5 Concluding Remarks
References
Parameterized Complexity of Graph Planarity with Restricted Cyclic Orders
1 Introduction
2 Preliminaries
3 FPQ-Choosable Planarity and Its Complexity
4 FPT Algorithm for FPQ-Choosable Planarity
5 FPQ-Choosable Planarity and NodeTrix Planarity
6 Open Problems
References
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
1 Introduction
1.1 Known Results
1.2 Our Results
2 Preliminaries
3 Algorithms
4 NP-Completeness Results
5 The Proofs of Theorems 1–3
6 Future Work
References
Classifying Subset Feedback Vertex Set for H-Free Graphs
1 Introduction
1.1 Our Results
2 Preliminaries
3 The Weighted Variant
3.1 Three Special Types of Solutions
3.2 Mim-Width
3.3 The Algorithm
4 The Unweighted Variant
5 Conclusions
References
Linearizing Partial Search Orders
1 Introduction
2 Preliminaries
3 The Partial Search Order Problem
4 One-Before-All Orderings
5 Partial LBFS Orders of Chordal Bipartite Graphs
6 Partial LBFS and MCS Orders of Split Graphs
7 Further Research
References
Minimum Weight Euclidean (1+)-Spanners
1 Introduction
2 Lower Bounds in the Plane
2.1 Lower Bounds for the Grid
2.2 Lower Bounds in the Unit Square
3 Spanner Algorithm: Sparse Yao-Graphs
3.1 Sparse Yao-Graph Algorithm
3.2 Stretch Analysis
4 Spanners in the Unit Square
5 Spanners for the Integer Grid
6 Outlook
References
Author Index