Local linear set on graphs with bounded twin cover number. (English) Zbl 1516.68066
Summary: Inspired by recent results for the so-called fair and local linear problems, we define two problems, Local Linear Set and Local Linear Vertex Cover. Here the task is to find a set of vertices \(X\subseteq V\) (which is a vertex cover) of the input graph \((V, E)\) such that the local linear constraints \(\ell(v)\leq | X\cap N(v)|\leq u(v)\) hold for all \(v\in V\); here, \(\ell(v)\) and \(u(v)\) are on the input. We prove that both problems are in FPT for the parameter twin cover number (using integer linear programming).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 90C10 | Integer programming |
References:
| [1] | Lin, L.-S.; Sahni, S., Fair edge deletion problems, IEEE Trans. Comput., 38, 756-761 (1989) · Zbl 1395.68213 |
| [2] | Kolman, P.; Lidický, B.; Sereni, J.-S., Fair edge deletion problems on treedecomposable graphs and improper colorings (2010) |
| [3] | Knop, D.; Koutecký, M.; Masařík, T.; Toufar, T., Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Log. Methods Comput. Sci., 15 (2019) · Zbl 1427.68125 |
| [4] | Knop, D.; Masařík, T.; Toufar, T., Parameterized complexity of fair vertex evaluation problems, (44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, LIPIcs, vol. 138 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 33 pp. · Zbl 1541.68292 |
| [5] | Masařík, T.; Toufar, T., Parameterized complexity of fair deletion problems, (Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017 (2017)), 628-642 · Zbl 1485.68192 |
| [6] | Jacob, A.; Raman, V.; Sahlot, V., Deconstructing parameterized hardness of fair vertex deletion problems, (Computing and Combinatorics - 25th International Conference, COCOON 2019. Computing and Combinatorics - 25th International Conference, COCOON 2019, LNCS, vol. 11653 (2019), Springer), 325-337 · Zbl 1534.68175 |
| [7] | Matoušek, J.; Nešetřil, J., Invitation to Discrete Mathematics (2009), Oxford University Press · Zbl 1152.05002 |
| [8] | Ganian, R., Improving vertex cover as a graph parameter, Discrete Math. Theor. Comput. Sci., 17, 77-100 (2015) · Zbl 1327.05321 |
| [9] | Eisenbrand, F.; Weismantel, R., Proximity results and faster algorithms for integer programming using the Steinitz lemma, (29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (2018), SIAM), 808-816 · Zbl 1410.90128 |
| [10] | Jansen, K.; Rohwedder, L., On integer programming and convolution, (10th Innovations in Theoretical Computer Science Conference, ITCS 2019. 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, LIPIcs, vol. 124 (2019), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 43 pp. · Zbl 1502.68138 |
| [11] | Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538-548 (1983) · Zbl 0524.90067 |
| [12] | Frank, A.; Tardos, E., An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, 7, 49-65 (1987) · Zbl 0641.90067 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
