4 papers
Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics
Jialiang Li, Aneta Neumann, Frank Neumann +2
Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algor…
Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
Jialiang Li, Weitong Chen, Mingyu Guo
Neural solvers provide fast solutions to graph combinatorial optimization problems, but training alone does not guarantee solution quality. Exact methods guarantee optimality but c…
Limited Query Graph Connectivity Test
Mingyu Guo, Jialiang Li, Aneta Neumann +2
We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are…
Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs
Mingyu Guo, Jialiang Li, Aneta Neumann +2
Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style at…