Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs
Authors: Shinwoo An, Yeonsu Chang, Kyungjin Cho, O-Joung Kwon, Myounghwan Lee, Eunjin Oh, Hyeonjun Shin
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, our main contributions are three-fold: a fixedparameter tractable algorithm for PAU-VC parameterized by clique-width, and linear-time algorithms for unit interval graphs and split graphs. In particular, the first algorithm improves the best-known algorithm for PAU-VC on trees significantly. We will provide the dynamic programming algorithm and prove the correctness. |
| Researcher Affiliation | Academia | 1 Department of Computer Science and Engineering, POSTECH, Pohang, South Korea 2 Department of Mathematics, Hanyang University, Seoul, South Korea 3 Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea |
| Pseudocode | No | The paper describes algorithms in prose and uses mathematical notation to define terms and outline methods (e.g., 'Now we describe a dynamic programming to solve PAU-VC for G.'). It does not contain any explicitly labeled 'Pseudocode' or 'Algorithm' blocks, nor does it present structured steps formatted like code. |
| Open Source Code | No | The paper does not contain any statements about releasing code, links to code repositories, or mentions of code in supplementary materials. |
| Open Datasets | No | The paper mentions benchmark datasets (e.g., TSPLIB, UCI, SATLIB, DIMACS) in the introduction as a motivation for generating graphs with unique solutions. However, the paper itself is theoretical and does not perform experiments using specific datasets, nor does it provide access information for any dataset it uses. The problem is discussed in a general graph-theoretic context. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving datasets, therefore, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Thus, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithms and proofs. It does not mention any specific software or programming languages with version numbers that would be required to reproduce experimental results. |
| Experiment Setup | No | The paper is theoretical and presents algorithms and proofs rather than empirical experiments. Consequently, it does not include details such as hyperparameters or system-level training settings. |