Preface
Organization
Contents
Proportionally Fair Matching with Multiple Groups
1 Introduction
1.1 Our Results and Contributions
1.2 Related Work
2 Preliminaries
3 A (14,1+4|OPT|)-Approximation for Proportionally Fair Matching
3.1 The Analysis
4 A Polynomial-Time Approximation in the -Limited Case
5 An Exact Algorithm for Proportionally Fair Matching
6 Hardness of Approximation for Proportionally Fair Matching
7 Conclusions
References
Reconstructing Graphs from Connected Triples
1 Introduction
1.1 Our Results
1.2 Related Work
2 Preliminaries
3 Algorithm for Finding Consistent Graphs from Triples
4 Unique Reconstruction of Trees
5 Further Reconstructible Graph Classes
6 Reconstruction from Connected k-Sets
7 Conclusion
References
Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1
1 Introduction
2 Preliminaries
3 FPT Algorithms for Pathwidth-One Vertex Explosion
3.1 Branching Algorithm
3.2 Quadratic Kernel
4 FPT Algorithms for Pathwidth-One Vertex Splitting
4.1 Linear Kernel
4.2 Branching Algorithm
5 FPT Algorithms for Splitting and Exploding to MSO2-Definable Graph Classes of Bounded Treewidth
6 Conclusion
References
Odd Chromatic Number of Graph Classes
1 Introduction
2 Preliminaries
3 Graphs of Bounded Degree and Graphs of Large Girth
4 Graphs of Bounded Modular-Width
5 Interval Graphs
6 Conclusion
References
Deciding the Erdős-Pósa Property in 3-Connected Digraphs
1 Introduction
2 Preliminaries
3 Digraphs with Neither Sources nor Sinks
4 Digraphs with Sources and Sinks
References
New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
1 Introduction
2 Preliminaries
3 O-Mim-Width
4 Neighbor-Depth of Graphs of Bounded Sim-Width
5 Conclusion
References
Nonplanar Graph Drawings with k Vertices per Face
1 Introduction
2 Basic Definitions
3 Density of k+-Real Face Graphs
3.1 k+-Real Face Graphs, with k 2
3.2 1+-Real Face Graphs
4 Density of Outer k+-Real Face Graphs
4.1 Outer k+-Real Face Graphs, with k 2
4.2 Outer 1+-Real Face Graphs
5 Inclusion Relationships
6 Open Problems
References
Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
1 Introduction
2 Preliminaries
2.1 Definitions
2.2 Our Results
3 Proof of Theorem 2 - Polynomial Cases
4 Proof of Theorem 2 - NP-Hard Cases
5 Proof of Theorem 1
6 Concluding Remarks
References
Cutting Barnette Graphs Perfectly is Hard
1 Introduction
2 Preliminaries
3 Proof of Theorem 1
3.1 Preparatory Lemmas
3.2 Reduction
3.3 G(I) Is Barnette
3.4 Properties of Variable and Crossing Gadgets
3.5 Properties of Clause Gadgets
3.6 Existence of Perfect Matching Cut Implies Satisfiability
3.7 Satisfiability Implies the Existence of a Perfect Matching Cut
References
Metric Dimension Parameterized by Treewidth in Chordal Graphs
1 Introduction
2 Preliminaries
2.1 Nice Clique Trees
2.2 Clique Separators and Resolving Sets
3 Algorithm Description
3.1 Extension of the Problem
3.2 Dynamic Programming
3.3 Algorithm
4 Proof of Theorem 1
References
Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
1 Introduction
2 Preliminaries
3 GL-Partition for Chordal Graphs
3.1 GL-Partition for Unweighted Chordal Graphs
3.2 GL-Partition for Weighted Chordal Graphs
4 GL-Partition for HHI42-free
References
Generating Faster Algorithms for d-Path Vertex Cover
1 Introduction
2 Fundamental Definitions and Basic Observations
3 The Output Algorithm and Its Correctness
4 The Generating Algorithm
4.1 Overview of the Algorithm
4.2 Color function
5 Generating Subgraph Branching Rules
5.1 Overview of the Approach
5.2 DominanceFree function
6 Applying (F,A,)-Algorithm to d-PVC
6.1 Handmade Rules
6.2 Obtained Results
7 Future Research Directions
References
A New Width Parameter of Graphs Based on Edge Cuts: -Edge-Crossing Width
1 Introduction
2 Preliminaries
3 Relationships Between Width Parameters
4 An FPT Approximation Algorithm for -Edge-Crossing Width
5 Algorithmic Applications on Coloring Problems
6 Conclusion
References
Snakes and Ladders: A Treewidth Story
1 Introduction
2 Preliminaries
3 Results
4 Future Work
References
Parameterized Results on Acyclic Matchings with Implications for Related Problems
1 Introduction
2 Preliminaries
3 FPT-Inapproximation Results
4 FPT Algorithm for AMBT
5 Conclusion and Future Research
References
P-Matchings Parameterized by Treewidth
1 Introduction
2 Preliminaries
3 Algorithm for Acyclic Matching
4 Algorithm for c-Disconnected Matching
5 Lower Bound for Disconnected Matching
6 Conclusion
References
Algorithms and Hardness for Metric Dimension on Digraphs
1 Introduction
2 Digraphs Whose Underlying Graph is a Tree
3 Orientations of Unicyclic Graphs
4 Modular Width
5 NP-Hardness for Restricted DAGs
6 Conclusion
References
Degreewidth: A New Parameter for Solving Problems on Tournaments
1 Introduction
2 Preliminaries
2.1 Notations
2.2 Links to Other Parameters
3 Degreewidth
3.1 Degreewidth of Regular Tournaments
3.2 Computational Complexity
3.3 An Approximation Algorithm to Compute Degreewidth
4 Results on Sparse Tournaments
4.1 U-Tournaments
4.2 A Polynomial Time Algorithm for Sparse Tournaments
5 Degreewidth as a Parameter
5.1 Dominating Set Parameterized by Degreewidth
5.2 FAST and FVST in Sparse Tournaments
6 Conclusion
References
Approximating Bin Packing with Conflict Graphs via Maximization Techniques
1 Introduction
1.1 Related Work
1.2 Techniques
1.3 Organization
2 Preliminaries
2.1 Coloring and Independent Sets
2.2 Bin Packing with Conflicts
2.3 Bin Packing Algorithms
3 Approximations for Perfect and Bipartite Graphs
4 Split Graphs
5 Asymptotic Hardness for Bipartite and Split Graphs
6 Discussion
References
i-Metric Graphs: Radius, Diameter and all Eccentricities
1 Introduction
2 General Case of i-Metric Graphs for Arbitrary i0
2.1 Centers of i-Metric Graphs
2.2 Approximating Radii and Diameters of i-Metric Graphs
2.3 Approximating all Eccentricities in i-Metric Graphs
3 Graphs with 1-Metric
3.1 The Eccentricity Function on 1-Metric Graphs is Almost Unimodal
3.2 Diameters of Centers of 1-Metric Graphs
3.3 Finding a Central Vertex of an 1-Metric Graph
References
Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor
1 Introduction
1.1 Our results
2 Preliminaries
3 PTAS for Minor-Free Graphs
3.1 Baker game
4 Hardness on 1-apex graphs
5 Future directions
References
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
1 Introduction
1.1 Our Results
2 Functionality
2.1 Finite Projective Planes
2.2 Upper Bound for General Graphs
2.3 Random Graphs
3 Symmetric Difference
3.1 Circular Arc Graphs
3.2 Interval Graphs
References
Cops and Robbers on Multi-Layer Graphs
1 Introduction
1.1 Further Related Work
1.2 Outline and Contributions
2 Definitions and Notation
3 Counter Examples and Anti-Monotonicity Results
4 Complexity Results
5 Extremal Multi-Layer Cop-Number
6 Multi-Layer Analogue of Meyniel's Conjecture
7 Conclusion and Open Problems
References
Parameterized Complexity of Broadcasting in Graphs
1 Introduction
2 Preliminaries
3 Telephone Broadcast Parameterized by the Cyclomatic Number
4 Telephone Broadcast Parameterized by the Vertex Cover Number
5 Kernelization for the Parameterization by k=n-t
6 Conclusion
References
Turán's Theorem Through Algorithmic Lens
1 Introduction
2 Algorithms
2.1 Compression Algorithm for r + 1
2.2 Looking for Larger Cliques
2.3 Independent Set above Turán's Bound
3 Lower Bounds
4 Conclusion
References
On the Frank Number and Nowhere-Zero Flows on Graphs
1 Introduction
1.1 Preliminaries
2 Theoretical Results
3 Algorithm
3.1 Results
References
On the Minimum Number of Arcs in 4-Dicritical Oriented Graphs
1 Introduction
2 The 4-Ore Digraphs and Their Properties
3 Proof of Theorem 8
References
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
1 Introduction
2 Preliminaries
3 Cut and Count for Modular-Treewidth
4 Reduction to Treewidth ()
5 Dynamic Programming Algorithms
5.1 Connected Vertex Cover
5.2 Feedback Vertex Set ()
References
Cops and Robber - When Capturing Is Not Surrounding
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Outline of the Paper
2 Relating the Different Versions
3 Explicit Graphs and Constructions
3.1 Complete Bipartite Graphs
3.2 Regular Graphs with Leaves
3.3 Graphs from Mutually Orthogonal Latin Squares
3.4 Line Graphs of Complete Graphs
4 When Capturing Is Not Surrounding
5 Conclusion
References
Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
1 Introduction and Results
2 Preliminaries
3 Proof of Theorem 4 and Theorem 5
3.1 The Reduction
4 Proof of Theorem 6
5 Conclusion
A Limits of Our Reduction in the Proof of Theorem 4
References
Upper Clique Transversals in Graphs
1 Introduction
2 Preliminaries
3 Intractability of UCT for Some Graph Classes
4 A Linear-Time Algorithm for UCT in Split Graphs
5 A Linear-Time Algorithm for UCT in Proper Interval Graphs
6 Conclusion
References
Critical Relaxed Stable Matchings with Two-Sided Ties
1 Introduction
2 Preliminaries
3 Algorithm for Computing CRITICAL-RSM
4 Correctness of Our Algorithm
5 Conclusion
References
Graph Search Trees and Their Leaves
1 Introduction
2 Preliminaries
3 Root Leaves
4 NP-Hardness of Branch Leaf Recognition
5 Branch Leaves and Chordal Graphs
References
Author Index