Combinatorial Algorithms, 31 Workshop, IWOCA 2020

Preface......Page 6
Organization......Page 8
Abstracts of Invited Talks......Page 12
Optimization by Population: Large-Scale Distributed Optimization Via Population Protocols......Page 13
Coordinating Swarms of Objects at Extreme Dimensions......Page 14
Algorithms for String Processing in Restricted-Access Models of Computation......Page 15
Contents......Page 16
Invited Paper......Page 19
 2 Traffic......Page 20
 3 Uniform Global Control for Particle Swarms......Page 22
 4 Online Triangulation and Structured Exploration......Page 23
 5 Cohesive Control......Page 25
 6 Coordinated Motion Planning......Page 26
 7 Constructing and Reconfiguring Large-Scale Structures......Page 27
 References......Page 28
Contributed Papers......Page 31
 1 Introduction......Page 32
 2 Preliminaries......Page 34
 3 Defining a Bubble Generator from a Spanning Tree......Page 36
  4.1 An Empirical Analysis of the Characteristics of the Bubble Generator Based on the Choice of the Spanning Tree......Page 39
  4.2 Application of the Bubble Generator to the Identification of AS Events in RNA-seq Data......Page 40
 5 Conclusions and Open Problems......Page 42
 References......Page 43
 1 Introduction......Page 45
 2 Preliminaries......Page 46
 3 Graph Parameters......Page 47
  3.1 Co-chromatic Number......Page 49
  3.2 Lettericity......Page 50
  3.3 Boxicity......Page 52
  3.4 H-Index......Page 53
  3.5 Achromatic Number......Page 54
 4 The Hierarchy......Page 55
 References......Page 56
 1 Introduction......Page 58
 2 Preliminaries......Page 60
  3.2 Tractable Cases......Page 61
 4 Structural Parameterizations......Page 64
 References......Page 69
 1 Introduction......Page 71
  2.1 Warm-Up Results......Page 73
  2.2 Using Larger Labels can be Arbitrarily Better......Page 74
 3 Complexity Aspects......Page 75
  3.1 NP-hardness for Planar Bipartite Graphs......Page 76
  3.2 Polynomiality for Bounded-Treewidth Graphs......Page 77
  4.1 Upper Bounds......Page 78
  4.2 General Conjecture and Refined Bounds for Bipartite Graphs......Page 80
 References......Page 82
 1 Introduction......Page 84
  1.3 Our Results......Page 86
 2 Preliminaries......Page 87
  2.1 Optimization Variant of Dominating Set Reconfiguration......Page 88
  2.2 Useful Observations......Page 89
  3.1 PSPACE-Completeness for Several Graph Classes......Page 90
  3.2 Linear-Time Algorithms......Page 92
  4.1 FPT Algorithm for Degeneracy and Solution Size......Page 93
  4.2 FPT Algorithm for Vertex Cover Number......Page 95
 References......Page 96
 1 Introduction......Page 98
 2 Preliminaries......Page 101
 3 Uniform Matroid......Page 103
 4 Laminar Matroid......Page 106
 5 Partition Matroid......Page 108
 References......Page 110
 1 Introduction......Page 112
 2 Preliminaries......Page 113
  2.1 Projective Geometry......Page 114
  2.2 Satisfiability Checking......Page 115
  2.3 Symbolic Computation and SAT+CAS......Page 116
  3.1 Basic SAT Encoding......Page 117
  3.2 Symmetry Breaking......Page 118
  4.2 Generating the Nonisomorphic 1-Factorizations......Page 120
  4.4 Solving the SAT Instances: Conquering......Page 121
  4.5 Certificate Verification......Page 122
 5 Conclusions and Future Work......Page 123
 References......Page 124
 1 Introduction......Page 127
 2 The Temporal Disjoint Branchings Problems......Page 130
 3 Temporal-Spanning Branchings......Page 132
  3.2 Edge-Disjoint Temporal-Spanning Branchings......Page 133
 4 Vertex-Spanning Branchings......Page 136
 5 Conclusions and Open Problems......Page 138
 References......Page 139
 1 Introduction......Page 141
  2.2 Saving n lgn -2n Bits......Page 146
 3 Optimal In-place Graph Algorithms......Page 147
 References......Page 152
 1 Introduction......Page 155
 2 The F-Node Deletion Problem and F-Edge Deletion Problem Without Advice......Page 157
 3 The Delayed H-Node Deletion Problem with Advice......Page 158
  3.1 Lower Bound......Page 159
  3.2 Upper Bound......Page 161
  4.1 Upper Bound......Page 163
  4.2 Lower Bound......Page 164
 References......Page 167
 1 Introduction......Page 169
  2.1 General Hardness Results......Page 173
  2.2 Bipartite Graphs and Their Line Graphs......Page 174
 3 Pseudo-Polynomial Algorithms for Special Graph Classes......Page 175
 References......Page 179
 1 Introduction......Page 181
 2 Notations and Definitions......Page 183
 3 Preliminary Analysis......Page 184
 4 Tracking Paths in Chordal Graphs and Tournaments......Page 185
 5 Approximation Algorithm and NP-Hardness of Tracking Paths in Bounded-Degree Graphs......Page 187
 6 Reconstructing Paths Using Trackers......Page 190
 7 Tracking Edge Set for Undirected Graphs......Page 191
 8 Conclusion......Page 192
 References......Page 193
 1 Introduction......Page 195
  1.1 Related Work......Page 196
  1.2 Our Results......Page 197
 2 Preliminaries......Page 198
  2.1 General Lower Bound......Page 199
  3.1 Lower Bound on SBP......Page 200
  3.2 Upper Bound on SBP......Page 201
 4 Uniform Revenues......Page 204
 5 Bipartite Graphs......Page 207
 References......Page 208
 1 Introduction......Page 210
  1.2 Neighborhood Diversity......Page 211
  1.4 Our Results and Related Work......Page 213
  2.1 Hardness......Page 215
  2.2 Neighborhood Diversity: An FPT Algorithm......Page 218
 3 Algorithms......Page 220
 4 Conclusion......Page 223
 References......Page 224
 1 Introduction......Page 226
 2 The Integer Version of PUF......Page 227
 3 Short Waiting Times......Page 231
 4 Rounding the Coordinates......Page 233
 References......Page 237
 1 Introduction......Page 239
 2 Nested Densest Subgraphs......Page 241
 3 Charges and Dipoles......Page 243
 4 Eliminating the Leaves......Page 244
 5 Eliminating and Separating the Cycle Components......Page 245
 6 Paths of Degree-2 Vertices and Cores......Page 247
 References......Page 250
On the Complexity of Singly Connected Vertex Deletion......Page 252
 1 Introduction......Page 253
 2 Preliminaries......Page 256
  3.1 Min-SCVD on -bounded Digraphs......Page 257
  3.2 Polynomial Time Algorithm for Min-SCVD on Acyclic Local Tournaments......Page 259
 4 Singly Connected Vertex Deletion on In-Tournaments......Page 261
 5 A Linear Kernel for SCVD on Local Tournaments......Page 262
 6 Conclusion......Page 263
 References......Page 264
 1 Motivation and Preliminaries......Page 266
  2.1 Background......Page 268
  2.2 Algorithm......Page 269
 3 Grids......Page 276
 References......Page 278
On the Complexity of Broadcast Domination and Metapost in Digraphs......Page 279
 1 Introduction......Page 280
 2 Preliminaries......Page 282
  3.1 Hardness Results......Page 283
  3.2 Complexity and Algorithms for (Layered) DAGs......Page 284
 4 Complexity of Metapost......Page 286
  4.1 Hardness Results......Page 287
  4.2 Algorithms......Page 288
 References......Page 290
 1 Introduction......Page 292
 2 Preliminaries......Page 294
 3 Plurality over Voters (PV)......Page 296
 4 Plurality over Districts (PD)......Page 300
 5 Concluding Remarks......Page 302
 References......Page 303
 1 Introduction......Page 304
 2 Preliminaries......Page 308
 3 Skyline Computation in High Dimension......Page 310
 4 Skyline Computation in Low Dimension......Page 311
  4.2 Domination Relationships Between Buckets......Page 312
  4.3 Algorithm and Bounds for Skyline Computation in Low Dimension......Page 314
 5 Skyline Lower Bound......Page 315
 References......Page 316
 1 Introduction......Page 319
 2 Preliminaries......Page 320
  3.2 SMTI......Page 322
  4.1 SMI......Page 326
 5 Conclusion......Page 329
 References......Page 330
 1 Introduction......Page 331
 2 Preliminaries......Page 334
 3 Outline of Proofs......Page 335
 4 Proofs of Theorems5 and 6......Page 337
 5 Proofs of Theorems7 and 8......Page 340
 6 Concluding Remarks......Page 343
 References......Page 344
The Steiner Problem for Count Matroids......Page 345
  1.1 Previous Work......Page 346
  1.2 Motivation and New Results......Page 347
  2.1 The Extension Operation......Page 348
  2.3 Feasibility, Components, and Sparse Input Graphs......Page 349
 3 Hardness Results......Page 350
 4 An Approximation Algorithm for the Metric Case......Page 351
 5 Optimal Solutions for Fixed |T| in the Metric Case......Page 353
  5.1 Reductions in Minimally Rigid Graphs......Page 354
 6 Concluding Remarks......Page 356
 References......Page 357
 1 Introduction......Page 358
 2 Degrees Bounded Min-Cost Group Steiner Tree Problem on Tree Inputs (Theorem 1)......Page 361
 3 A Relation Between Min-Degree Steiner k-Tree and Min-Degree Group Steiner Tree (Theorem 2)......Page 364
 4 An O(log3 n) Approximation for Min-Degrees Group Steiner Tree on Bounded Treewidth Graphs (Theorem 3)......Page 366
 References......Page 368
 1 Introduction......Page 370
 2 Preliminaries......Page 373
 4 Proof of the Case (b) of Theorem 2......Page 375
 5 Proof of the Case (d) of Theorem 2......Page 377
  6.1 Planar Graphs......Page 378
  6.2 Bipartite Graphs......Page 379
  6.3 Graphs with Big Girth......Page 380
 References......Page 381
 1 Introduction......Page 383
  1.1 Related Work......Page 384
  1.2 Our Results......Page 385
 2 Preliminaries......Page 386
  3.1 Previous Approach......Page 387
  3.2 Improvement to Previous Approach: Eligible Trees......Page 388
  3.3 An Improved Modified Algorithm......Page 390
  3.4 Inapproximability......Page 392
  4.1 Budgeted Edge-Vertex Domination......Page 393
 5 Conclusion......Page 394
 References......Page 395
 1 Introduction......Page 397
  2.1 Definitions......Page 399
  2.2 Relationship to Covering Arrays......Page 400
  3.1 Moser-Tardos-Style Column Resampling Algorithm......Page 401
  3.2 Conditional Expectation Heuristic Search Algorithm......Page 402
  3.3 Homogeneity Post-Optimization......Page 404
 4 Results......Page 405
 5 Conclusion......Page 408
 References......Page 409
 1 Introduction......Page 410
 2 Statement of Problems......Page 411
 3 Motivation and Related Work......Page 412
 4 Main Results......Page 414
 6 The 2-PVCB Problem......Page 419
 7 Conclusion......Page 421
 References......Page 422
 1 Introduction......Page 424
  3.1 Comb-Convex Bipartite Graphs......Page 426
  3.2 Dually Chordal Graphs......Page 427
  4.1 Split Graphs......Page 428
  4.2 Proper Interval Graphs......Page 430
 5 Inapproximation Results......Page 432
 6 APX-Completeness......Page 434
 7 Conclusion......Page 435
 References......Page 436
Author Index......Page 437