Algorithms and Discrete Applied Mathematics: 8th International Conference, CALDAM 2022, Puducherry, India, February 10–12, 2022, Proceedings

Preface
Organization
Abstracts of Invited Talks
	All-Pairs Shortest Paths and Fine-Grained Complexity
	Linear Programming and its Uses in Algorithm Design
	Approximation Algorithms for Some Geometric Optimization Problems
	Contents
Graph Theory
A Proof of the Multiplicative 1-2-3 Conjecture
	1 Introduction
	2 Proof of Theorem 1
	References
Chromatic Bounds for Some Subclasses of (P3P2)-free graphs
	1 Introduction
	2 Preliminaries
	3 {P3P2, (K1K2)+Kp}-free graphs
	4 {P3P2, 2K1+Kp}-free graphs
	References
List Homomorphisms to Separable Signed Graphs
	1 Motivation and Background
	2 Path-Separable Signed Graphs
	3 Cycle-Separable Signed Graphs
	4 Conclusions
	References
Some Position Problems for Graphs
	1 Introduction
	2 The Smallest Graph with Given mp- and gp-Numbers
	3 The Largest Size of Graphs with Given Order and Position Numbers
	4 The Diameters of Graphs with Given Order and mp-Number
	References
Comparability Graphs Among Cover-Incomparability Graphs
	1 Introduction
	2 Ptolemaic Graph
	3 Cograph and Distance-Hereditary Graph
	4 Bisplit Graphs
	5 Composition of C-I Graphs
	References
Graph Algorithms
Complexity of Paired Domination in AT-free and Planar Graphs
	1 Introduction
	2 Preliminaries
		2.1 Basic Notations and Definitions
		2.2 AT-free Graphs
	3 Approximation Algorithm
	4 Exact Polynomial-Time Algorithm
	5 Paired Domination in Planar Graphs
	6 Concluding Remarks
	References
The Complexity of Star Colouring in Bounded Degree Graphs and Regular Graphs
	1 Introduction
	2 Definitions
	3 Bounded Degree Graphs
		3.1 4-Star Colouring
		3.2 5-Star Colouring
	4 Regular Graphs
	5 Conclusion
	References
On Conflict-Free Spanning Tree: Algorithms and Complexity
	1 Introduction
	2 Preliminaries
	3 Computational Complexity
	References
B0-VPG Representation of AT-free Outerplanar Graphs
	1 Introduction
		1.1 Literature
		1.2 Terminology and Notation
	2 Linear Outerplanar Graphs
	3 B0-VPG Representation of 2-connected Linear Outerplanar Graphs
	4 Concluding Remarks
	References
P Versus NPC: Minimum Steiner Trees in Convex Split Graphs
	1 Introduction
	2 STREE in Split Graphs with Convexity on I
		2.1 Star-Convex Split Graphs
		2.2 Comb-Convex Split Graphs
		2.3 Path-Convex Split Graphs
	3 STREE in Split Graphs with Convexity on K
		3.1 Tree-Convex Split Graphs
	References
On cd-Coloring of {P5,K4}-free Chordal Graphs
	1 Introduction
	2 Preliminaries
	3 {P5,K4}-free Chordal Graphs
	4 P6-free Chordal Bipartite Graphs
	5 Conclusion
	References
An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs
	1 Introduction
		1.1 Paper Organization
	2 An Application of DAG SSSP Method to Arbitrary Digraphs
	3 An Output-Sensitive APSP Algorithm for DAGs
	4 A Potential Extension to Digraphs with Large Cycles
	5 Final Remarks
	References
Covering a Graph with Densest Subgraphs
	1 Introduction
	2 Definitions
		2.1 Algorithms for Densest Subgraph
	3 A Polynomial Time Algorithm for the k-Densest Cover Subgraphs
	4 An Approximation Algorithm for Top k-Cover-Densest Subgraphs
	5 Conclusions and Open Problems
	References
Computational Geometry
Coresets for (k, )-Median Clustering Under the Fréchet Distance
	1 Introduction
		1.1 Related Work
		1.2 Our Contributions
		1.3 Organization
	2 Coresets for Generalized k-Median Clustering in Metric Spaces
		2.1 Sensitivity Bound
		2.2 Coresets by Sensitivity Sampling
	3 Coresets for (k,)-Median Clustering Under the Fréchet Distance
	4 Towards Practical (1,)-Median Approximation Algorithms
	5 Conclusion
	References
Bounds and Algorithms for Geodetic Hulls
	1 Introduction
		1.1 Related Work
		1.2 Contribution
	2 Preliminaries
	3 Bounds for the Gin of the Graph Contour
	4 Bounding the Hull Number
	5 Experimental Results
		5.1 Graph Hull Sets and Gin
	6 Conclusions and Future Work
	References
Voronoi Games Using Geodesics
	1 Introduction
		1.1 Previous Results
		1.2 New Results
	2 Preliminaries
		2.1 Orthogonal Convex Polygons for the L 1 Metric
		2.2 Orthogonal Convex Polyhedra
	3 Bounds for Orthogonal Convex Polygons
		3.1 Orthogonal Convex Polygon with Clients on Boundary
	4 Bounds for Orthogonal Convex Polyhedra
		4.1 Orthogonal Convex Polyhedra with Boundary Clients
	References
Algorithms and Optimization
Approximation and Parameterized Algorithms for Balanced Connected Partition Problems
	1 Introduction
		1.1 Our Contribution
	2 Approximation Algorithm for Min-Max BCPk
	3 Parameterized Algorithm for 1-MAX-MIN BCP
	4 Concluding Remarks
	References
Algorithms for Online Car-Sharing Problem
	1 Introduction
	2 Preliminaries
		2.1 Problem Setting and Notations
		2.2 -Net-Cost Augmenting Path
	3 The Online-Match-and-Assign Algorithm
	4 Algorithm Analysis
		4.1 Adversarial Order of Arrivals
		4.2 Random Order of Arrivals
	5 Conclusion
	References
Algebraic Algorithms for Variants of Subset Sum
	1 Introduction: Variants of Subset Sum
		1.1 Main Results
		1.2 Technical Overview
		1.3 Prior Works and Their Limitations
	2 Preliminaries and Notations
	3 Proof of Theorem 1
	4 Proof of Theorem 2
	5 Conclusion
	References
Hardness and Approximation Results for Some Variants of Stable Marriage Problem
	1 Introduction
	2 Preliminaries
	3 Complete Stable Matching in SMTI-C and SMTI-STEP
		3.1 COM SMTI-C Problem
		3.2 COM SMTI-STEP Problem
	4 Maximum Stable Matching in SMTI-INC Problem
	5 Minimum Stable Matching in SMTI-STEP Instance
	6 Approximation Algorithm for MIN SMTI-INC
	7 Conclusion
	References
On Fair Division with Binary Valuations Respecting Social Networks
	1 Introduction
		1.1 Related Work
		1.2 Our Contributions
	2 Preliminaries
	3 Envy-Freeness
		3.1 NP-Hardness for Two Agent Types
		3.2 W-Hardness Parameterized by Goods
		3.3 W-Hardness Parameterized by Vertex Cover
		3.4 NP-Hardness on Paths
	4 Proportionality for Graphs
		4.1 Local Proportionality: NP-hardness
		4.2 Quasi-Global Proportionality: Efficient Algorithms
	References
Parameterized Intractability of Defensive Alliance Problem
	1 Introduction
		1.1 Our Main Results
		1.2 Known Results
	2 Hardness Results of Defensive Alliance
		2.1 Proof of Theorem 1
		2.2 Proof of Theorem 2
	3 Conclusions
	References
On the Approximability of Path and Cycle Problems in Arc-Dependent Networks
	1 Introduction
	2 Statement of Problems
	3 Computational Complexity of SNCC and LoNCC
	4 Fixed-Parameter Algorithm for SP
		4.1 Intuition
		4.2 Randomized Algorithm
		4.3 Proof of Correctness
		4.4 Derandomization
	5 Lower Bound on Kernel Size for the SP Problem
	6 Conclusion
	References
Approximation Algorithms in Graphs with Known Broadcast Time of the Base Graph
	1 Introduction
	2 Exact Algorithm When the Base Graph is a k-Regular mbgs with One Tree
		2.1 Broadcast Algorithm When Originator is r
	3 Linear Time 1.5-Approximation Algorithm for General Hypercube of Trees
	4 Linear Time Constant Approximation Algorithm in Graph of Trees with Known Broadcast Time of the Base Graph
	5 Conclusion and Future Work
	References
Author Index