Preface
A Good Tradition
The Newest Edition: Cochem 2024
Highlights of the Conference
Finally, Big Thanks …
Organization
Contents
Invited Paper
The Information Extraction Framework of Document Spanners - A Very Informal Survey
1 Document Spanners
2 Representations of Document Spanners
2.1 Regular Spanners
2.2 Core-Spanners
3 Problems on Regular Spanners and Core Spanners
4 An Approach to Tame Core Spanners
5 Regular Spanners on SLP-Compressed Data
5.1 Updates
References
Contributed Papers
Generalized Distance Polymatrix Games
1 Introduction
1.1 Related Work
2 Our Contribution
3 Preliminaries
4 Existence of (,k)-Equilibria
5 (,k)-PoA of General Graphs
5.1 (,k)-PoA: Upper Bound
5.2 (,k)-PoA: Lower Bound
6 (1,k)-PoS of General Graphs
7 (,k)-PoA of Bounded-Degree Graphs
7.1 (,k)-PoA: Upper Bound
7.2 (,k)-PoA: Lower Bound
8 Conclusion and Future Works
References
Relaxed Agreement Forests
1 Introduction
2 Preliminaries, Basic Properties and Bounds
3 Hardness of MRAF
4 Exact Algorithms
5 Approximation Algorithms
6 Implementation and Experimental Observations
7 Discussion and Open Problems
References
On the Computational Complexity of Generalized Common Shape Puzzles
1 Introduction
2 Preliminaries
3 Complexity of Shape Logic Puzzle
4 Undecidability of Common Multiple Shape Puzzle
4.1 Undecidability of a Generalized Jigsaw Puzzle
4.2 Undecidability of the Common Multiple Shape Puzzle
5 Improved Solutions for Common Multiple Shapes
6 Concluding Remarks
References
Fractional Bamboo Trimming and Distributed Windows Scheduling
1 Introduction
2 Background
3 Fractional Bamboo Trimming
4 Distributed Windows Scheduling
5 Conclusion
References
New Support Size Bounds and Proximity Bounds for Integer Linear Programming
1 Introduction
2 Subset Sum Distinct Sets
2.1 One-Dimensional Subset Sum Distinct Sets
2.2 Higher-Dimensional Subset Sum Distinct Sets
2.3 Numerical Results
3 Support Size Bounds for Integer Linear Programming
3.1 Single-Constraint ILPs
3.2 ILPs with Multiple Constraints
3.3 Numerical Results
4 Bounds on Largest Graver Basis Elements
4.1 Numerical Results
4.2 Proximity
References
On the Parameterized Complexity of Minus Domination
1 Introduction
2 Preliminaries
3 Twin-Cover
4 Cluster Vertex Deletion Set
5 Distance to Disjoint Components and Component Size
References
Exact and Parameterized Algorithms for Choosability
1 Introduction
2 Preliminaries
3 Exact Algorithms
4 Cutwidth
5 Other Structural Parametrizations
5.1 Polynomial Kernel Parameterized by Vertex Cover
5.2 Dual Parameterization
5.3 Clique-Modulator Parameterization
5.4 Split Graphs
6 Conclusion
References
Parameterized Algorithms for Covering by Arithmetic Progressions
1 Introduction
2 Preliminaries
3 Algorithm for Cover By Arithmetic Progressions (CAP)
4 FPT Algorithm for Exact Cover by Arithmetic Progressions
5 Strong NP-Hardness of Cover by Arithmetic Progressions in Zp
6 Parameterization Below Guarantee
References
Row-Column Combination of Dyck Words
1 Introduction
2 Preliminaries
3 Row-Column Combination of Dyck Languages
3.1 Matching-Graph Circuits
4 A Sublanguage Preserving Characteristic Dyck Words Properties
5 Conclusion
References
Group Testing in Arbitrary Hypergraphs and Related Combinatorial Structures
1 Introduction
2 Notations and Terminology
3 Non-adaptive Group Testing for General Hypergraphs
4 Combinatorial Structures for Group Testing in Arbitrary Hypergraphs
5 Upper Bound on the Size of (E, q,m,)-Selectors
5.1 A Non-adaptive Group Testing Algorithm for General Hypergraph
5.2 A Two-Stage Group Testing Algorithm for General Hypergraphs
5.3 A Three-Stage Group Testing Algorithm for General Hypergraphs
References
On the Parameterized Complexity of the Perfect Phylogeny Problem
1 Introduction
2 Definitions and Preliminary Results
3 Main Results
4 XALP Membership of Triangulating Colored Graphs
5 Zipper Chains and Gadgets
6 XALP-Hardness of Triangulating Multicolored Graphs
7 Future Research
References
Data Reduction for Directed Feedback Vertex Set on Graphs Without Long Induced Cycles
1 Introduction
2 Preliminaries
3 DFVS in Graphs Without Long Induced Cycles
4 Nowhere Dense Classes Without Long Induced Cycles
5 DFVS in Planar Graphs Without Long Cycles
6 Long Induced Cycles
References
Visualization of Bipartite Graphs in Limited Window Size
1 Introduction
2 The Two Layer Setting
2.1 Hardness of Minimizing Average Window Size.
2.2 Minimizing Average Window Size for Fixed Children
3 The Two Ring Setting
4 Conclusions and Open Problems
References
Outerplanar and Forest Storyplans
1 Introduction
2 Preliminaries
3 Separation of Graph Classes
4 Outerplanar Storyplans
5 Forest Storyplans
6 Open Problems
References
The Complexity of Cluster Vertex Splitting and Company
1 Introduction
2 Preliminaries
3 NP-Completeness of Sigma Clique Cover
4 NP-Completeness of Cluster Vertex Splitting
5 A Linear Kernel for Cluster Vertex Splitting
5.1 The Notions of Valency and Critical Cliques
5.2 Towards a Rule to Shrink Critical Cliques
5.3 Towards a Rule to Recognize Negative Instances
5.4 Deriving the Kernel
6 The Critical-Clique Lemma
7 The Complexity of Cluster Editing With Vertex Splitting
8 Conclusion
References
Morphing Graph Drawings in the Presence of Point Obstacles
1 Introduction
2 Preliminaries and Basic Observations
3 Proof of Theorem 1
4 Open Problems
References
Word-Representable Graphs from a Word's Perspective
1 Introduction
2 Preliminaries
3 k-Circle Representation
4 Graphs of Conjugate Words
5 Graphs Represented by k-Local Words
6 The Language of a Graph
7 Conclusion
References
The Complexity of Online Graph Games
1 Introduction
2 Gadget Reductions
3 A Reduction Framework for Online Vertex Subset Games
4 Vertex Cover
5 More Vertex Subset Problems
6 Conclusion
References
Removable Online Knapsack with Bounded Size Items
1 Introduction
2 Upper Bounded Item Size
2.1 Lower Bounds on the Competitive Ratio
2.2 Upper Bounds on the Competitive Ratio
3 Lower Bounded Item Size
3.1 Lower Bounds on the Competitive Ratio
3.2 Upper Bounds on the Competitive Ratio
4 Conclusion and Directions for Future Work
References
Faster Winner Determination Algorithms for (Colored) Arc Kayles
1 Introduction
1.1 Partisan Variants of Arc Kayles
1.2 Related Work
1.3 Our Contribution
1.4 Preliminaries
2 A Polynomial Kernel for Colored Arc Kayles
3 Arc Kayles for Trees Parameterized by Vertex Cover Number
4 Arc Kayles for Trees
5 NP-Hardness of BW-Arc Kayles
References
Automata Classes Accepting Languages Whose Commutative Closure is Regular
1 Introduction
2 Preliminaries
3 Known Results
4 Circular Automata over a Binary Alphabet
5 Structural Conditions on Automata
6 The Group Hierarchy
7 The Positive Variety W
8 Conclusion
References
Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching
1 Introduction
2 Basic Notions
3 Extracting the Shortest Characteristic Factors with the Use of Finite Automaton
3.1 The Shortest Characteristic Factors DFAs
4 Positive Position Run and Its Computation Using Pattern Matching of Characteristic Factors
5 Conclusion and Future Work
References
Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages
1 Introduction
2 Preliminaries
2.1 Boolean Algebras and Symbolic Automata
2.2 Equivalence Class and Representatives for 3SFA
2.3 Learning Model
3 Our Proposed Algorithm
3.1 3SFA Generator
3.2 Finding a Minimal Separating SFA
4 Correctness and Query Complexity
5 Heuristics for Finding a Closed Grouping
6 Evaluation
6.1 Comparison in Separation: Exact vs Heuristic Methods
6.2 Comparison in Learning: SFA vs DFA
7 Concluding Remarks
References
Apportionment with Thresholds: Strategic Campaigns are Easy in the Top-Choice but Hard in the Second-Chance Mode
1 Introduction
2 Preliminaries
3 Classical Top-Choice Mode
4 Experiment
5 The Second-Chance Mode
6 Conclusions
References
Local Certification of Majority Dynamics
1 Introduction
1.1 Our Results
1.2 Related Work
2 Preliminaries
2.1 Majority and Finite State Dynamics
3 Certification Upper-Bounds
3.1 Upper-Bound for Election-Prediction
4 Lower-Bounds
References
Complexity of Spherical Equations in Finite Groups
1 Introduction
2 Notation and Problem Description
3 Fixed Finite Groups and Cayley Tables
4 The Groups Sn and An
5 Spherical Equations in Dihedral Groups
6 Spherical Equations for Two-by-Two Matrices
6.1 Spherical Equations in GL(2,p)
7 Matrix Groups in Higher Dimensions
7.1 The Groups ZmkC2
8 Open Problems
References
Positive Characteristic Sets for Relational Pattern Languages
1 Introduction
2 Notation and Preliminary Results
2.1 Positive Characteristic Sets
2.2 Relational Pattern Languages
3 Reversal Relation
4 Equal-Length Relation
5 Conclusions
References
Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
1 Introduction
1.1 Our Techniques
2 Preliminaries
3 Turing Kernel
4 Proof of Theorem 1: The Algorithm
5 Theorem 3: Lower Bound
6 Concluding Remarks
References
The Weighted HOM-Problem Over Fields
1 Introduction
2 Preliminaries and Technical Background
3 A Pumping Lemma Over Fields
4 The Tetris-Free Weighted HOM-Problem
5 Conclusion
References
Combinatorics of Block-Parallel Automata Networks
1 Introduction
2 Definitions
3 Counting Block-Parallel Update Modes
3.1 Intersection of Block-Sequential and Block-Parallel Modes
3.2 Partitioned Orders
3.3 Partitioned Orders up to Dynamical Equality
3.4 Partitioned Orders up to Isomorphism on the Limit Dynamics
3.5 Implementations
4 Conclusion and Perspectives
References
On the Piecewise Complexity of Words and Periodic Words
1 Introduction
2 Words, Subwords and Simon's Congruence
3 The Piecewise Complexity of Words
3.1 Defining Words via Their Subwords
3.2 Reduced Words and the Minimality Index
3.3 Fundamental Properties of Side Distances
3.4 Relating h and
3.5 Subword Complexity and Concatenation
4 Computing h(u) and (u)
5 Arch Factorizations and the Case of Periodic Words
5.1 Arch-Jumping Functions
5.2 Arch Factorization of Periodic Words
5.3 Piecewise Complexity of Periodic Words
6 Conclusion
References
Distance Labeling for Families of Cycles
1 Introduction
2 Preliminaries
2.1 Warm-Up: Labeling Directed Cycles
2.2 Basic Facts on Labeling Undirected Cycles
3 More Efficient Labeling Scheme and Its Analysis
4 Chain Labelings vs Optimal Labelings
5 Discussion and Future Work
References
On the Induced Problem for Fixed-Template CSPs
1 Introduction
2 Preliminaries
2.1 Multi-sorted CSPs
2.2 The Lifted Language
3 The Construction
3.1 Example: Binary and Conservative Operations
4 The Complexity of CSP+B()
4.1 Conditions for the Tractability of B
5 Reductions of CSP(B) to CSP()
6 Conclusions
References
Correction to: Parameterized Algorithms for Covering by Arithmetic Progressions
Correction to: Chapter 9 in: H. Fernau et al. (Eds.): SOFSEM 2024: Theory and Practice of Computer Science, LNCS 14519, https://doi.org/10.1007/978-3-031-52113-3_9
Author Index