{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:12:29Z","timestamp":1740809549760,"version":"3.38.0"},"reference-count":21,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2025,3,1]]},"DOI":"10.1587\/transinf.2024fcp0009","type":"journal-article","created":{"date-parts":[[2024,7,31]],"date-time":"2024-07-31T22:19:21Z","timestamp":1722464361000},"page":"214-220","source":"Crossref","is-referenced-by-count":0,"title":["An FPT Algorithm for the Exact Matching Problem and NP-Hardness of Related Problems"],"prefix":"10.1587","volume":"E108.D","author":[{"given":"Hitoshi","family":"MURAKAMI","sequence":"first","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yutaro","family":"YAMAGUCHI","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[2] A. D\u00fcrr, N. El Maalouly, and L. Wulf, \u201cAn approximation algorithm for the exact matching problem in bipartite graphs,\u201d Proc. 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2023), no.18, pp.18:1-18:21, 2023. 10.4230\/LIPIcs.APPROX\/RANDOM.2023.18"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[3] J. Edmonds, \u201cPaths, trees, and flowers,\u201d Canadian Journal of Mathematics, vol.17, pp.449-467, 1965. 10.4153\/cjm-1965-045-4","DOI":"10.4153\/CJM-1965-045-4"},{"key":"3","unstructured":"[4] N. El Maalouly, \u201cExact matching: algorithms and related problems,\u201d Proc. 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), no.29, pp.29:1-29:17, 2023. 10.4230\/LIPIcs.STACS.2023.29"},{"key":"4","unstructured":"[5] N. El Maalouly, S. Haslebacher, and L. Wulf, \u201cOn the exact matching problem in dense graphs,\u201d arXiv:2401.03924, 2024."},{"key":"5","unstructured":"[6] N. El Maalouly and R. Steiner, \u201cExact matching in graphs of bounded independence number,\u201d Proc. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), no.46, pp.46:1-46:14, 2022. 10.4230\/LIPIcs.MFCS.2022.46"},{"key":"6","unstructured":"[7] N. El Maalouly, R. Steiner, and L. Wulf, \u201cExact matching: correct parity and FPT parameterized by independence number,\u201d Proc. 34th International Symposium on Algorithms and Computation (ISAAC 2023), no.28, pp.28:1-28:18, 2023. 10.4230\/LIPIcs.ISAAC.2023.28"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[8] S. Fortune, J. Hopcroft, and J. Wyllie, \u201cThe directed subgraph homeomorphism problem,\u201d Theoretical Computer Science, vol.10, no.2, pp.111-121, 1980. 10.1016\/0304-3975(80)90009-2","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[9] A. Galluccio and M. Loebl, \u201cOn the theory of Pfaffian orientations. I. Perfect matchings and permanents,\u201d Electronic Journal of Combinatorics, vol.6, R6, pp.1-19, 1999. 10.37236\/1438","DOI":"10.37236\/1438"},{"key":"9","unstructured":"[10] H.-F. Geerdes and J. Szab\u00f3, \u201cA unified proof for Karzanov\u2019s exact matching theorem,\u201d EGRES Quick Proofs, no.2011-02, 6pp., 2011."},{"key":"10","doi-asserted-by":"crossref","unstructured":"[11] A.V. Karzanov, \u201cMaximum matching of given weight in complete and complete bipartite graphs,\u201d Cybernetics, vol.23, no.1, pp.8-13, 1987. 10.1007\/bf01068796","DOI":"10.1007\/BF01068796"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[12] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 6th Ed., Springer, 2018. 10.1007\/978-3-662-56039-6","DOI":"10.1007\/978-3-662-56039-6"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[13] D. Lokshtanov, N.S. Narayanaswamy, V. Raman, M.S. Ramanujan, and S. Saurabh, \u201cFaster parameterized algorithms using linear programming,\u201d ACM Transactions on Algorithms, vol.11, no.2, pp.1-31, 2014. 10.1145\/2566616","DOI":"10.1145\/2566616"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[14] L. Lov\u00e1sz, \u201cMatching structure and the matching lattice,\u201d Journal of Combinatorial Theory, Series B, vol.43, no.2, pp.187-222, 1987. 10.1016\/0095-8956(87)90021-9","DOI":"10.1016\/0095-8956(87)90021-9"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[15] K. Mulmuley, U.V. Vazirani, and V.V. Vazirani, \u201cMatching is as easy as matrix inversion,\u201d Combinatorica, vol.7, no.1, pp.105-113, 1987. 10.1007\/bf02579206","DOI":"10.1007\/BF02579206"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[16] R. Niedermeier and P. Rossmonith, \u201cOn efficient fixed-parameter algorithms for weighted vertex cover,\u201d Journal of Algorithms, vol.47, no.2, pp.63-77, 2003. 10.1016\/s0196-6774(03)00005-1","DOI":"10.1016\/S0196-6774(03)00005-1"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[17] C.H. Papadimitriou and M. Yannakakis, \u201cThe complexity of restricted spanning tree problem,\u201d Journal of the ACM, vol.29, no.2, pp.285-309, 1982. 10.1145\/322307.322309","DOI":"10.1145\/322307.322309"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[18] B. Reed, K. Smith, and A. Vetta, \u201cFinding odd cycle transversals,\u201d Operations Research Letters, vol.32, no.4, pp.299-301, 2004. 10.1016\/j.orl.2003.10.009","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"18","unstructured":"[19] I. Schlotter and A. Seb\u0151, \u201cOdd paths, cycles and <i>T<\/i>-joins: connections and algorithms,\u201d arXiv:2211.12862, 2022."},{"key":"19","unstructured":"[20] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003."},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] T. Yi, K.G. Murty, and C. Spera, \u201cMatchings in colored bipartite networks,\u201d Discrete Applied Mathematics, vol.121, no.1-3, pp.261-277, 2002. 10.1016\/s0166-218x(01)00300-6","DOI":"10.1016\/S0166-218X(01)00300-6"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[22] R. Yuster, \u201cAlmost exact matching,\u201d Algorithmica, vol.63, no.1-2, pp.39-50, 2012. 10.1007\/s00453-011-9519-0","DOI":"10.1007\/s00453-011-9519-0"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E108.D\/3\/E108.D_2024FCP0009\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T03:33:37Z","timestamp":1740800017000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E108.D\/3\/E108.D_2024FCP0009\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2024fcp0009","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2025,3,1]]},"article-number":"2024FCP0009"}}